LeetCodeの解題向上について(二)

今日1本の問題に出会って、言わざるを得なくて、構想はすべてを決定して、私の解題の心の道の過程と大物の解題の方式に対する解析と感想を分かち合います.
 

820.単語の圧縮符号化

テーマの出所:https://leetcode-cn.com/problems/short-encoding-of-words/
 
単語リストを与え、このリストをインデックス文字列SとインデックスリストAとに符号化する.
たとえば、このリストが["time","me","bell"]の場合、S="time#bell#",indexes=[0,2,5]と表すことができます.
各インデックスについては、文字列S内のインデックスの位置から文字列の読み取りを開始し、「#」が終了するまで、前の単語リストを復元できます.
では、与えられた単語リストを符号化することに成功した最小文字列の長さはどのくらいですか.
 
例:
入力:words=["time","me","bell"]出力:10説明:S="time#bell#",indexes=[0,2,5]. 
ヒント:
1 <= words.length <= 20001 <= words[i].length<=7各単語は小文字です.
 
 
簡単にテーマの要求を説明します:例えばtimeとme、私はtimeの接尾辞なので削除して、time#の中からme#を見つけることができて、再びtime#me#を創立する必要がなくて、このように最も短い文字列の長さを形成しました.
 
私の考え:最初は1つの集合(目的の重さを除く)を創立して、wordsの中の文字列を集合の中に保存して、それから集合にアクセスして、現在の文字列の接尾辞を削除します.最後に集合(すべての文字列の長さ+1)を加えると、最終的な最短長になります.書き上げた後は過ぎても動作が遅く、公式解析を見てコードを以下のように最適化した(substrで接尾辞を削除できるのか、熟練していないのか).
 
もちろん、この問題は辞書の木で解決することもできますが、空間の複雑さは比較的大きいです(実はコードの簡潔さが好きです).

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

 
複雑度が高く、指数級です.
次は大物の考えを分かち合います(驚きました).
 
まず、どの言語でも、文字列をソートするコンテナは常に辞書順に来ているので、time->emit me->em dell->lledなどのすべての文字列を逆順序にする法則を見つけることができます.このとき、私たちは再びソートします.emがemitの前にあるかどうか、私たちはもっと簡単にemを見つけて削除することができます.いずれの文字列も辞書順に1つずつ除外でき、最後に接尾辞が存在しない文字列が残ります.
 
大物コード:

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        for(auto &s : words){
            reverse(s.begin(),s.end());
        }
        sort(words.begin(),words.end());
        int res=0;
        for(int i=0;i1;i++){
            int size=words[i].size();
            if(words[i]==words[i+1].substr(0,size)) continue;
            res+=size+1;
        }
        return res+words.back().size()+1;
    }
};

コードリンク:https://leetcode-cn.com/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/313014
 
 
考えが強すぎるとしか言いようがない.
 
カードを打つ:文字列に出会って接尾辞をやり直し、まず集合、辞書ツリーを考え、辞書順のソートを反転します.