LeetCode——查找常用字符

╰+攻爆jí腚メ 2022-12-15 08:34 118阅读 0赞

## 题目 ##

给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

**示例 1：**

输入：\["bella","label","roller"\]

输出：\["e","l","l"\]

**示例 2：**

输入：\["cool","lock","cook"\]

输出：\["c","o"\]

**提示：**

1 <= A.length <= 100

1 <= A\[i\].length <= 100

A\[i\]\[j\] 是小写字母

## **题解** ##

从题目中可以得出以下几条信息：

*  仅有小写字母组成，小写字母共26个
 *  包含重复字符，意思是不能单纯的判定字符是否在所有字符串中出现，还有按出现次数判定

## 解题思路 ##

根据题目要求，如果一个字符c在每个字符串中出现了n次及以上，则最后的答案中要包含n个字符c。因此我们可以用数据minfrep\[c\]来存储字符c在所有字符串中出现的最小次数。

依次遍历每个字符串，当遍历字符串s时，使用frep\[c\]统计s中每一个字符c出现的次数。统计结束后再讲每一个minfrep\[c\]更新为minfrep\[c\]与frep\[c\]中的最小值。这样当遍历完所有的字符串后，minfrep\[c\]存储的就是字符c在所有字符串中出现的最小次数。

最后遍历minfrep\[c\]，构造出答案。

### 代码实现 ###

class Solution {
        public List<String> commonChars(String[] A) {
            int[] minfrep = new int[26];
            Arrays.fill(minfrep, Integer.MAX_VALUE);
            for (String word: A) {
                int[] frep = new int[26];
                for (int i=0; i<word.length(); ++i) {
                    ++frep[word.charAt(i)-'a'];
                }
                for (int i=0; i<26; ++i) {
                    minfrep[i] = Math.min(frep[i], minfrep[i]);
                }
            }
            List<String> res = new ArrayList<>();
            for (int i=0; i<26; ++i) {
                for (int j=0; j<minfrep[i]; ++j){
                    res.add(String.valueOf((char)(i+'a')));
                }
            }
            return res;
        }
    }

## 复杂度分析 ##

**时间复杂度：**![O(n(m+\\left | \\sum \\right |))][O_n_m_left _ _sum _right]，其中n是数组A的长度，m是字符串的平均长度，![\\sum][sum]是字符集（即26个小写字母，![\\left | \\sum \\right |][left _ _sum _right]=26）

*  遍历所有字符串并统计frep的时间复杂度为![O(nm)][O_nm];
 *  使用frep更新minfrep的时间复杂度为![O(n\\left | \\sum \\right |)][O_n_left _ _sum _right]；
 *  由于最终答案包含的字符个数不会超过最短的字符串长度，因此构造最终答案的时间复杂度为![O(m+\\left | \\sum \\right |)][O_m_left _ _sum _right]，可以忽略

**空间复杂度：![O(\\left | \\sum \\right |)][O_left _ _sum _right]**，这里不计算存储答案的空间，只使用了freph和minfrep，它们的长度为![\\left | \\sum \\right |][left _ _sum _right]

[O_n_m_left _ _sum _right]: https://private.codecogs.com/gif.latex?O%28n%28m&plus;%5Cleft%20%7C%20%5Csum%20%5Cright%20%7C%29%29
[sum]: https://private.codecogs.com/gif.latex?%5Csum
[left _ _sum _right]: https://private.codecogs.com/gif.latex?%5Cleft%20%7C%20%5Csum%20%5Cright%20%7C
[O_nm]: https://private.codecogs.com/gif.latex?O%28nm%29
[O_n_left _ _sum _right]: https://private.codecogs.com/gif.latex?O%28n%5Cleft%20%7C%20%5Csum%20%5Cright%20%7C%29
[O_m_left _ _sum _right]: https://private.codecogs.com/gif.latex?O%28m&plus;%5Cleft%20%7C%20%5Csum%20%5Cright%20%7C%29
[O_left _ _sum _right]: https://private.codecogs.com/gif.latex?O%28%5Cleft%20%7C%20%5Csum%20%5Cright%20%7C%29