1002. Find Common Characters

1002. Find Common Characters Easy

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

1
2

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

1
2

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 100
3. A[i][j] is a lowercase letter

思路：

思路一：暴力破解

仅供参考：

• 找到长度最小的字符串，由于是考虑每一个字符串中重复的元素
• 将这个字符串放到 map 中，map 中的值可以设为字符串数组长度
• 依次遍历，如果重复就 -1 ，最后看 map 中的值是否变为 0

思路二：哈希

可以结合下面的图和代码进行理解

• 由于都是小写字母，只需要使用容量为 26 的数组表示 26 位字母；
• 第一个 26 位数组，将字符串数组的第一个字符串装下，重复的 + 1
• 后面和第一个一样操作得到新的数组，比较其中的值，取最小 的即可，因为最小的那个才代表着它在自己的数组中重复了多少次，在所有的字符串中，它最多的字符重复
• 将结果放在第一个数组，继续比较

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public List<String> commonChars(String[] A) {
    // 哈希表
    int[] res = new int[26];
    for (int i = 0; i < A[0].length(); i++) {
        res[A[0].charAt(i) - 'a']++;
    }
    for (int i = 1; i < A.length; i++) {
        int[] temp = new int[26];
        for (int j = 0; j < A[i].length(); j++) {
            temp[A[i].charAt(j) - 'a']++;
        }

        for (int j = 0; j < 26; j++) {
            res[j] = Math.min(res[j], temp[j]);
        }
    }
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < 26; i++) {
        while (res[i] != 0) {
            ans.add(String.valueOf((char)((i) + 'a')));
            res[i]--;
        }
    }
    return ans;
}