[C++]LeetCode:113 Word Break II(DP&&Backtacking)解分割組合せ

6414 ワード
LeetCode dynamic programming バックパッキング
タイトル:
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s =  "catsanddog" , dict =  ["cat", "cats", "and", "sand", "dog"] .
A solution is  ["cats and dog", "cat sand dog"] .
Answer 1:BF再帰解TLE
考え方:現在の結果セットを維持するたびに、残りのすべてのサブストリングを巡回し、サブストリングが辞書内に表示される場合は、結果を保存します.次のレイヤに残りのすべての文字を再帰します.
しかし、このやり方はLeetcodeでタイムアウトします.
Error Code: 
class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> ret;
        if(s.size() == 0) return ret;
        wordBreak_helper(s, dict, 0, "", ret);
        return ret;
    }
    
private:
    void wordBreak_helper(string s, unordered_set<string>& dict, int pos, string tmp, vector<string>& ret)
    {
        if(pos == s.size())
        {
            ret.push_back(tmp.substr(0, tmp.size()-1));  //    
            return;
        }
        
        for(int i = pos; i < s.size(); i++)
        {
            for(int j = 1; j < s.size()-i; j++)
            {
                string substr = s.substr(pos, j);
                if(dict.find(substr) != dict.end())
                {
                    wordBreak_helper(s, dict, i+1, tmp + " " + substr, ret);
                }
            }
        }
    }
};

Answer 2:DPを入れる
考え方:この問題は、Word Breakの動的計画の考え方を参考にしています.しかし、今回は各分割結果を記録する必要があるため、2次元配列を使用して動的計画結果を保存し、2次元配列形式vectordp、dp[i]は文字列が座標iから始まるすべての合法的な単語の終了位置リストを表す.文字列の末尾から動的計画配列を下から上へ解き,現在のstopを終了位置とし,すべての合法的な開始位置をループし,サブ列が辞書内にある場合,対応するdp配列に要素を追加する.なお、現在のstopから一致する辞書内の単語がない場合(ここでは切れないことを説明する)、このstopをスキップしてカットオフ位置を行うことができる.
すべての可能な組合せを解いた後,遡及法により,すべての可能な分割状況を解いた.今回は上から下へ求め,文字列の先頭からすべての結果を文字列の末尾に達するまで遍歴する.
Attention:
1.stopの意味は、単語終了座標の下位、すなわち次の単語の先頭または文字列lengthを表す.だからstopはs.size()から始まります.
for(int stop = s.size(); stop >= 0; stop--)

2.現在のstopから辞書内の単語がない場合は、このブレークポイントをスキップできます.
 //   stop         ，        stop       (stop               )
            if(stop < s.size() && mark[stop].empty()) continue;

3.現在のstopの前のビットから、すべての合法的な開始位置をループし、動的計画配列を更新します.
/     stop  ，            ，    mark 。
            for(int start = stop - 1; start >= 0; start--)
            {
                string substr = s.substr(start, stop - start);
                if(dict.find(substr) != dict.end())
                {
                    mark[start].push_back(stop);
                }
            }

4.C++11のforの新しい使い方.
for文では、簡単な範囲反復が可能になります.
int my_array[5] = {1, 2, 3, 4, 5};
for (int &x : my_array)
{
  x *= 2;
}

for文の第1の部分は、一般的なforループで宣言されたパラメータのように、範囲反復のために使用されるパラメータを定義し、その役割ドメインはループの範囲のみである.「:」の後の第2のブロックは、反復される範囲を表します.また、ループ変数は参照であり、ループ内で値を変更できます.
for(int& stop : mark[index])
プログラムでは,この文はindexで始まるすべての単語をループするstop位置を表す.
5.遡及する際、現在のpathを維持することに注意し、pathの代わりにサブストリングを追加した新しいストリングを使用することはできない.これは循環文であるため、次のstopは元のpath(サブストリングを追加しない)を使用する.
for(int& stop : mark[index])
        {
            string substr = s.substr(index, stop - index);
            string newpath = path + (index == 0 ? substr : " " + substr);

AC Code: 
class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        //mark[i]    i    ，              。
        vector<list<int>> mark(s.size(), list<int>());
        
        //        
        for(int stop = s.size(); stop >= 0; stop--)
        {
            //   stop         ，        stop       (stop               )
            if(stop < s.size() && mark[stop].empty()) continue;
            //     stop  ，            ，    mark 。
            for(int start = stop - 1; start >= 0; start--)
            {
                string substr = s.substr(start, stop - start);
                if(dict.find(substr) != dict.end())
                {
                    mark[start].push_back(stop);
                }
            }
        }
        
        vector<string> ret;
        generate(mark, 0, s, "", ret);
        return ret;
    }

private:
    void generate(vector<list<int>> mark, int index, const string& s, string path, vector<string>& ret)
    {
        for(int& stop : mark[index])
        {
            string substr = s.substr(index, stop - index);
            string newpath = path + (index == 0 ? substr : " " + substr);
            if(stop == s.size())
                ret.push_back(newpath);
            else
                generate(mark, stop, s, newpath, ret);
        }
    }
};

この問題は総合性が強く,DPとBacktrackingを結合し,難易度が高く,特にdp配列を構築する際の方法は重点的に参考にすることができる.
私のc++学習(5)switch文の詳細
c++におけるプロセスの保留