3839. 前綴連接組的數目

思路

只是單純要相同前綴有幾個字串，用哈希表紀錄即可

程式碼

哈希表

class Solution {
public:
    int prefixConnected(vector<string>& words, int k) {
        unordered_map<string, int> umap; // 紀錄同樣前綴的字串出現了郭少次
        for(string& s : words) {
            if(s.size() >= k) {
                string prefix = s.substr(0, k);
                umap[prefix]++;
            }
        }
        int res = 0;
        for(auto& [k, v] : umap) {
            if(v >= 2) { // 包含兩個單字，才算一組
                res++;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$