820. Short Encoding of Words

這題我一開始先排序, string長度越大的放前面, 然後依序加到res裡, 從尾端進行find, 一旦找不到, 或是找到了, 但這個字的結尾並不是 “#”, 就會往res加,

但結果會TLE, 時間複雜度為O(K * N²) K為字的長度, n為總共的字數量

class Solution {
public:
    static bool sortString(string A, string B){
        return A.size() > B.size();
    }
    int minimumLengthEncoding(vector<string>& words) {
        sort(words.begin(), words.end(), sortString);
        string res = "";
        for(auto word : words){
            auto pos = res.rfind(word);
            if(pos == string::npos || res[pos + word.size()] != '#'){
                res += word + "#";
            }
        }
        return res.size();
    }
};

看到一種用set的做法, 這實在是太驚艷了, 他會把所有的word都塞到一個set, 然後挑每個word, 刪掉他們的後綴,

例如

time 就刪掉 ime, me, e
me 就刪掉, e
等等
可以發現 time 在刪掉me的時候, 就把多餘的字串也給刪掉了

時間複雜度為O(N * K²), K 題目說最大為7, 所以這個會比較小

class Solution {
public:
   
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> m(words.begin(), words.end());
        for(auto w: words){
            for(int i = 1;i < w.size();i++){
                m.erase(w.substr(i));
            }
        }
        int res = 0;
        for(auto w: m){
           res += w.size() + 1;
        }
        return res;
    }
};