(哈希表) 1002. 查找共用字符 ——【Leetcode每日一题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了(哈希表) 1002. 查找共用字符 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❓1002. 查找共用字符

难度：简单

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

示例 1：

输入：words = [“bella”,“label”,“roller”]
输出：[“e”,“l”,“l”]

示例 2：

输入：words = [“cool”,“lock”,“cook”]
输出：[“c”,“o”]

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 由小写英文字母组成

💡思路：哈希表计数

“小写英文字母“，“出现频率”，这些关键字都是为 哈希法 量身定做的！！！

使用数组统计出搜索每个字符串里26个字符的出现的频率；
然后取每个字符频率最小值；
- 刚开始用以一个字符串对 hash 数组进行初始化，
- 两两比较，取最小值；
最后转成输出格式。

🍁代码：(Java、C++)

Java

class Solution {
    public List<String> commonChars(String[] words) {
        List<String> ans = new ArrayList<>();
        int[] hash = new int[26];
        for(char c : words[0].toCharArray()){//用第一个字符串给hash数组初始化
            hash[c - 'a']++;
        }
        int[] hashOther = new int[26];
        for(int i = 1; i < words.length; i++){
            Arrays.fill(hashOther, 0);//重置为0
            for(char c : words[i].toCharArray()){//统计剩余字符串中每个字符数量
                hashOther[c - 'a']++;
            }
            //对比26个字符，取最小值
            for(int j = 0; j < 26; j++){
                hash[j] = Math.min(hash[j], hashOther[j]);
            }
        }
        for(int i = 0; i < 26; i++){//将字符转换为String型
            while(hash[i] > 0) {
                ans.add(String.valueOf((char)('a' + i)));
                hash[i]--;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<string> ans;
        int hash[26] = {0};
        for(char c : words[0]){//用第一个字符串给hash数组初始化
            hash[c - 'a']++;
        }
        int hashOther[26] = {0};
        for(int i = 1; i < words.size(); i++){
            memset(hashOther, 0, 26 * sizeof(int));//重置为0
            for(char c : words[i]){//统计剩余字符串中每个字符数量
                hashOther[c - 'a']++;
            }
            //对比26个字符，取最小值
            for(int j = 0; j < 26; j++){
                hash[j] = min(hash[j], hashOther[j]);
            }
        }
        for(int i = 0; i < 26; i++){//将字符转换为string型
            while(hash[i]--) {
                ans.push_back(string(1, i + 'a'));
            }
        }
        return ans;
    }
};

🚀 运行结果：

(哈希表) 1002. 查找共用字符 ——【Leetcode每日一题】

🕔 复杂度分析：

时间复杂度： $O (n (m + ∣ Σ ∣))$ ，其中 n 是数组 words 的长度（即字符串的数目），m 是字符串的平均长度， $\Sigma$ 为字符集，在本题中字符集为所有小写字母， $|\Sigma|=26$ 。
空间复杂度： $O(∣\Sigma∣)$ ，这里只计算存储答案之外的空间。我们使用了数组 hash 和 hashOther，它们的长度均为 $|\Sigma|$ ,这里为 26。