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.DFS
1.先找字符串的前缀，找到一个前缀，然后把这个前缀放到路径里面，
2.然后对剩下的字符串，再重复第一步。
直到字符串搜索结束。
其中还有个trick是，如果字符串的前缀不会超过字典里最长的字符串长度。
这个方法能够应付一般的情况，但是在leetcode上最复杂的case时候会超时。。。。
2. 动态规划
这个做法其实是第一题的变形。但是这个变形很巧妙。这个思路说了也很直接。但是也很巧妙。
先回忆一下，第一题work break是怎么做的。在字符串位置为I处，判断此I是不是wordbreakable，
1. 那么从字符串头上开始，找wordbreakbale的位置k，然后检查这个K和I之间的子字符串是不是在字典里
2.如果在字典里，那么位置I是wordbreakable的。
3.如果不在字典里，那么继续往前找，直到K到I 位置，那么这个I肯定不是wordbreakable的。
在结束的时候
直接查wordbreak[N]就是结果。
但是路径信息完全没有保留下来。
比如catsanddog, cat|s|and|dog|
其中|为该位置可以分割，但是如果直接拿这个wordbreakable 标记数组来切词，肯定不对，比如s就不在字典里面。
那怎么做呢？考虑到图的adj 那就也可以搞一个类似的结构。
0
1 c NULL
2 a NULL
3 t 0
4 s 0
5 a NULL
6 n NULL
7 d 3,4
8 d NULL
9 o NULL
10 g 7
然后从最后一个字符开始做一个遍历就搞定了。
void backtrack(string s, vector<list<int>>& lookup, int index, vector<string>& result, vector<string> path) { if (index == 0)//reach the end { string str; int size = path.size(); for (int i =size - 1; i >= 0; i--) { str.append(path[i]); if (i!=0)str.append(" "); } result.push_back(str); return; } list<int>::iterator it = lookup[index].begin(); for (; it != lookup[index].end(); it++) { int prev = *it; path.push_back(s.substr(prev, index - prev)); backtrack(s, lookup, prev, result, path); path.pop_back(); } } vector<string> wordBreak(string s, unordered_set<string> &dict) { int size = s.length(); vector<bool> wordbreak(size + 1); vector<list<int>> lookup(size + 1); vector<string> result; vector<string> path; wordbreak[0] = true; for (int index = 1; index <= size; index++) { for (int prev = 0; prev<index; prev++) { if (wordbreak[prev] && dict.find(s.substr(prev, index - prev)) != dict.end()) { //found a match str wordbreak[index] = true; lookup[index].push_back(prev); } } } // here we got // 1 . whether string breakable wordbreak[n], // 2. lookup matrix like a graph if (!wordbreak[size]) return result; backtrack(s, lookup, size, result, path); return result; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。