1002. 查找共用字符

Problem: 1002. 查找共用字符

关键词小写字母 重复字符

用一个哈希表记录第一个字符串的字符出现次数

在使用一个hash表记录之后字符串的字符出现次数

注意每次第二个哈希表记录完毕之后要置零

错误

没有置零第二个hash表

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(n)$

Code

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {

        int* hash = new int[26]();

        for(int i = 0;i < words[0].size(); i++) {
            hash[ words[0][i] - 'a']++;
        }

        int* hashOrt = new int[26]();

        for(int i = 1; i < words.size(); i++) {
            memset(hashOrt, 0, 26 * sizeof(int));//hashOrt置零
            for(int j = 0; j < words[i].size(); j++ ) {
                hashOrt[ words[i][j] - 'a']++;
            }
            for(int j = 0; j < 26; j++) {
                hash[j] = min(hash[j],hashOrt[j]);
            }
        }

        vector<string> result;

        for(int i = 0; i < 26; i++) {
            while(hash[i] > 0) {
                string s(1,i + 'a');
                result.push_back(s);
                hash[i]--;
            }    
        }

        delete[] hash;
        delete[] hashOrt;

        return result;
    }
};