LintCode (107) Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Have you met this question in a real interview? 

Yes

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

又是TLE。。。o(n^2)...但是过不了大数据，TLE了。。。先贴个简单的，再仔细分析怎么弄吧。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: /** * @param s: A string s * @param dict: A dictionary of words dict */ bool wordBreak(string s, unordered_set<string> &dict) { // write your code here int n=s.size(); vector<bool> tbl(n+1, false); tbl[0]=true; for (int i=1; i<=n; i++){ for (int j=0; j<i; j++){ if (tbl[j] && dict.find(s.substr(j,i-j))!=dict.end()){ tbl[i]=true; break; } } } return tbl[n]; } };

简单的优化就是从后往前找，找到set里面最大的长度为止，这样复杂度就变成o(n,max(string.size())了。。。蛋疼。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: /** * @param s: A string s * @param dict: A dictionary of words dict */ bool wordBreak(string s, unordered_set<string> &dict) { // write your code here int n=s.size(); vector<bool> tbl(n+1, false); tbl[0]=true; int maxLen=getMaxLength(dict); for (int i=1; i<=n; i++){ for (int j=i-1; j>=0 && j>=i-maxLen; j--){ if (tbl[j] && dict.find(s.substr(j,i-j))!=dict.end()){ tbl[i]=true; break; } } } return tbl[n]; } int getMaxLength(unordered_set<string> &dict){ unordered_set<string>::iterator it=dict.begin(); int len=INT_MIN; for(;it!=dict.end();++it){ len= max(len, (int)(*it).size()); } return len; } };