[LeetCode] 1002. Find Common Characters

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

Example 1:
Input: words = [“bella”,”label”,”roller”]
Output: [“e”,”l”,”l”]

Example 2:
Input: words = [“cool”,”lock”,”cook”]
Output: [“c”,”o”]

Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

查找共用字符。

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

思路

题意是给一个装了单词的数组，请求出这些单词里面共同的字母，以 list 形式输出。如果有多个相同的字母也需要多次输出。

思路是用 hashmap 记录 input 中第一个单词里面每个字母的出现次数，然后从第二个单词开始，也是去计算每个字母出现的次数，但是把某个字母在某个单词中出现的最少的次数加入结果集。举个例子，比如 cool 里面 o 出现了两次，但是在 lock 里面 o 只出现了一次，记录 o 的时候只记录最少的出现次数。最后遍历结果集里面每个单词，根据次数拼接成最后要输出的 list。

复杂度

时间O(m * n) - n 个单词 * 每个单词的平均长度 m
空间O(n)

代码

Java实现

class Solution {
    public List<String> commonChars(String[] words) {
        String first = words[0];
        int[] map = new int[26];
        for (char c : first.toCharArray()) {
            map[c - 'a']++;
        }

        int n = words.length;
        for (int i = 1; i < n; i++) {
            String cur = words[i];
            int[] letters = new int[26];
            for (char c : cur.toCharArray()) {
                letters[c - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                map[j] = Math.min(map[j], letters[j]);
            }
        }

        List<String> res = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            while (map[i] != 0) {
                char c = (char) (i + 'a');
                res.add(c + "");
                map[i]--;
            }
        }
        return res;
    }
}