力扣5978——统计追加字母可以获得的单词数（哈希表、状态压缩）

本文主要是介绍力扣5978——统计追加字母可以获得的单词数（哈希表、状态压缩），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：这题当时陷到统计频率去了，还一直没解决越界的问题，结束后解决越界但超时。统计每个字符串的字母出现频率，按滑动窗口，只比较长度大小差为1的字符串，看是否满足条件。

//超时
class Solution {
public:
    bool isok(vector<int>& s, vector<int>& t) {
        bool flag = 0;
        for(int i = 0; i < 26; i++) {
            t[i]--;
            if(t == s) {
                flag = true;
                break;
            }
            t[i]++;
        }
        return flag;
    }
    int wordCount(vector<string>& start, vector<string>& target) {
        int n = start.size(), m = target.size();
        sort(start.begin(), start.end(), [](const auto& a, const auto& b) {
            return a.size() < b.size();
        });
        sort(target.begin(), target.end(), [](const auto& a, const auto& b) {
            return a.size() < b.size();
        });
        vector<vector<int>> countstart(n, vector<int>(26, 0));
        vector<vector<int>> counttarget(m, vector<int>(26, 0));
        for(int i = 0; i < n; i++) {
            for(auto x : start[i]) {
                countstart[i][x-'a']++;
            }
        }
        for(int i = 0; i < m; i++) {
            for(auto x : target[i]) {
                counttarget[i][x-'a']++;
            }
        }
        int startp = 0;
        int ans = 0;
        for(int i = 0; i < m; i++){
            while(startp < n && start[startp].size() + 1 < target[i].size()) {
                startp++;
            }
            if(startp == n) break;
            if(start[startp].size() + 1 > target[i].size()) {
                continue;
            }
            if(start[startp].size() + 1 == target[i].size()) {
                for(int j = startp; j < n && start[j].size() + 1 == target[i].size(); j++) {
                    if(isok(countstart[j], counttarget[i])) {
                        ans++;
                        break;
                    }
                }
            }
        }
        return ans;       
    }
};

可以通过的思路是将所有可以生成的字符串按字母序重排后放入set，对每个target，重排字母序后看在set是否出现。

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        unordered_set<string> hash;
        int ans = 0;
        for(auto s : startWords) {
            string tmp = s;
            for(char i = 'a'; i <= 'z'; i++) {
                if(tmp.find(i) == tmp.npos) {
                    tmp += i;
                    sort(tmp.begin(), tmp.end());
                    hash.insert(tmp);
                    tmp = s;
                }
            }
        }
        for(auto t : targetWords) {
            sort(t.begin(), t.end());
            if(hash.find(t) != hash.end()) ans++;
        }
        return ans;
    }
};

另一种更高效的思路，是用二进制表示该位是否有字母出现。

因为题目说明每个字母只出现一次，则每个字符串的状态就是一个长度为26的2进制数组，每一位代表该字母是否出现过，这样用一个int整数就可以表示一个可以生成的字符串，对每个target在set中找它对应整数即可。

这里涉及到位运算，<< 代表左移，即该字母位置对应位置标记为1；|或运算是加上该位的情况；&与运算是看该位是否已有字母，整体思路跟上一方法相同，只是用int表示一个string。

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        unordered_set<int> hash;
        int ans = 0;
        for(auto s : startWords) {
            int tmp = 0;
            for(auto c : s) tmp |= (1 << (c - 'a'));
            for(int i = 0; i < 26; i++) {
                if(!(tmp & (1 << i))) {
                    hash.insert(tmp | (1 << i));
                }
            }
        }
        for(auto t : targetWords) {
            int tmp = 0;
            for(auto c : t) tmp |= (1 << (c - 'a'));
            if(hash.find(tmp) != hash.end()) ans++;
        }
        return ans;
    }
};

这篇关于力扣5978——统计追加字母可以获得的单词数（哈希表、状态压缩）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！