查找常用字符

LeetCode每日一题，1002. Find Common Characters

先看题目描述

大意就是给定一个给定仅由小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表

算法和思路

计数法

根据题目要求，如果字符 c 在所有字符串中均出现了 k 次及以上，那么最终答案中需要包含 k 个 c。那么我们可以使用 counts[c - ‘a’] 存储字符 c 在所有字符串中出现次数的最小值

然后我们依次遍历每一个字符串，用 temp[c - ‘a’] 存储每个字符 c 在该字符串中出现的次数。在遍历一个字符串结束后，我们更新每一个 counts[c - ‘a’] 为其自身与 temp[c - ‘a’] 中较小的那个值。这样一来，遍历完所有字符串后，counts[c - ‘a’] 就存储了字符 c 在所有字符串中出现次数的最小值

在构造最终的答案时，我们遍历所有的小写字母 c，并将 counts[c - ‘a’] 个 c 添加进 res 数组，最后返回 res 数组即可

算法源码

import java.util.*;

class Solution {
    public List<String> commonChars(String[] A) {
        List<String> res = new ArrayList<>();
        int[] counts = new int[26];
        for (int i = 0; i < counts.length; i++) {
            counts[i] = Integer.MAX_VALUE;
        }
        for (String s: A) {
            int[] temp = new int[26];
            for (char c: s.toCharArray()) {
                temp[c - 'a'] += 1;
            }
            for (int i = 0; i < 26; i++) {
                counts[i] = Math.min(counts[i], temp[i]);
            }
        }
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] == Integer.MAX_VALUE) continue;
            for (int j = 0; j < counts[j]; j++) {
                res.add(String.valueOf((char)('a' + i)));
            }
        }
        return res;
    }
}