Word Break II
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"].
难度是5星级了。
难度指数直逼word ladder II了
主要的难点： 要优化到极致，不能直接使用递归回溯法，否则超时。
本程序方法：
1 使用二维表vector
2 利用二维表优化递归回溯法。
优化点：
如果当前位置是start，但是tbl[start]为空，那么就是说，这个break位置不能break整个s串的，直接返回上一层，不用搜索到下一层了。
这样的优化结果是：
如果遇到大数据如：
Input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
Expected: []
输出结果是空，那么使用本程序，运行时间，只是构建动态规划法表使用了O(n*n)时间复杂度(实际运行是O(n))，递归回溯的时候时间是O(1)，就可以返回结果了。
这也是本题的考查重点：很多大数据的例子都是返回[]空结果。
当然，如果知道出题者是这样来考我们的，那么我们可以直接排除这种情况，也是可以过的。那么难度指数就会直降至3到4星级了。
本程序是连打带消地对付了这种情况效率是十分高的了，有12ms运行时间的战果。
比网上很多博客的程序要优化，关键是动态规划表的构建功力，本程序的构建方法应该是最优的。有能改进的欢迎指教。
class Solution {
public:
//2014-2-19 update
vector
wordBreak(string s, unordered_set
&dict) { vector
rs; string tmp; vector
> tbl = genTable(s, dict); word(rs, tmp, s, tbl, dict); return rs; } void word(vector
&rs, string &tmp, string &s, vector
> &tbl, unordered_set
&dict, int start=0) { if (start == s.length()) { rs.push_back(tmp); return; } for (int i = 0; i < tbl[start].size(); i++) { string t = s.substr(start, tbl[start][i]-start+1); if (!tmp.empty()) tmp.push_back(' '); tmp.append(t); word(rs, tmp, s, tbl, dict, tbl[start][i]+1); while (!tmp.empty() && tmp.back() != ' ') tmp.pop_back();//tmp.empty() if (!tmp.empty()) tmp.pop_back(); } } vector
> genTable(string &s, unordered_set
&dict) { int n = s.length(); vector
> tbl(n); for (int i = n - 1; i >= 0; i--) { if(dict.count(s.substr(i))) tbl[i].push_back(n-1); } for (int i = n - 2; i >= 0; i--) { if (!tbl[i+1].empty())//if we can break i->n { for (int j = i, d = 1; j >= 0 ; j--, d++) { if (dict.count(s.substr(j, d))) tbl[j].push_back(i); } } } return tbl; } };