EEPW论坛

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"].

思路：

我们从第一个字母开始，遍历字典，看从第一个字母开始能组成哪个在字典里的单词，如果找到了一个，就在这个单词的结束位置的下一个字母处，建立一个列表，记录这个词（保存到一个列表的数组）。当遍历完成这个词典并找出所有以第一个字母开头的词以后，我们进入下一轮搜索。下一轮搜索只在之前找到的词后面位置开始，如果这个位置不是一个词的下一个字母位置，我们跳过，这样我们相当于构建了一个树（实际上是列表数组）。每个找到的词都是这个树的一个分支，有了这个“”树“”，然后我们在用深度优先搜索，把路径加到当中就行。

1. class Solution  

2. {  

3. public:  

4.     void countBreak(string& s, int index, string str,  

5.                             vector<int>& dp, unorderd_set<string>& dict,   

6.                             vector<string>& res, int &length)  

7.     {  

8.         string substr;  

9.         for (int len=1; index+len<=length; ++len)  

10.         {  

11.             if (dp[index+len] && dict.find(s.substr(index, len))!=dict.end())  

12.             {  

13.                 substr = s.substr(index,len);  

14.                 if (index+len>=length)  

15.                 {  

16.                     res.push_back(str+substr);  

17.                 }  

18.                 else  

19.                 {  

20.                     countBreak(s, index+len, str+substr+" ", dp, dict, res, length);  

21.                 }  

22.             }  

23.         }  

24.     }  

25.     vector<string> wordBreak(string s, unordered_set<string>& dict)  

26.     {  

27.         int len = s.size();  

28.         vector<string> res;  

29.         if (len<1)  

30.         {  

31.             return res;  

32.         }  

33.   

34.         vector<int> dp(len+1, 0);  

35.         dp[0] = 1;  

36.   

37.         for (int i=1; i<=len; i++)  

38.         {  

39.             for (int j=i-1; j>=0; --j)  

40.             {  

41.                 if (dp[j] && dict.find(s.substr(j, i-j)!=dict.end())  

42.                 {  

43.                     dp[i] = 1;  

44.                 }  

45.             }  

46.         }  

47.   

48.         if (dp[len]==0)  

49.         {  

50.             return res;  

51.         }  

52.   

53.         countBreak(s, 0, "", dp, dict, res, len);  

54.         return res;  

55.     }  

56. };