Getting rid of TLE

• if you are getting TLE despite the correct DP or DFS solution, it might be because the largest test input is like this

["aa..(lots of 'a').b", "a","aaaaa"...so on]

As you can see this test case should return empty as last character in input string is b, which is not in the dictionary. So all the work in DP/DFS is a waste

To escape from TLE, just put a check first whether the input string s is breakable or not..if breakable then try to break it using your algo

• Works perfectly with Word Break!

• What is a breakable check?

• It could be just the function you use to deal with word break I. :)

• Actually add the checking of whether the word is breakable is not sufficient. What about replace the end character from b to a? Your algorithm still gets TLE.

• Well, the number of solutions in that case would go from 0 to exponential in input length, so any algorithm computing all solutions would get TLE...

• You could just add the whole string to the dictionary. Then it would be breakable per definition, and the solution would be just the whole string. However, most backtracking algos will probably get a TLE then..

• @vimukthi
You do need to do that. You did that in your program actually. The key is in case of unbreakable, you put empty list in dp. Next time, get to the same start, your dfs just return empty list.

dp.put(start, words);

If you don't save empty list, it will get TLE. Following change will get TLE.

if (words.size() > 0) {
dp.put(start, words);
}

• You can actually write the DP in a recursive way; I mean, backtracking. It will calculate possible solutions only when s is breakable. Please refer to https://discuss.leetcode.com/topic/38054/python-easy-to-understand-solution

• @hunter9 said in Getting rid of TLE:

Actually add the checking of whether the word is breakable is not sufficient. What about replace the end character from b to a? Your algorithm still gets TLE.

if you replace the only character from b to a, the size of answer will be over 5E+44, which means no device can store the answer.

• A really easy solution that works for any approach is to just have an 'effort' counter that bails if no progress is being made. Thus, an acceptable solution is not related to any particular approach.

class Solution {
public:
int effort;

void helper(string &s, vector<string> &wordDict, int si, vector<int> &thisSltn, vector<string> &allSltn) {
if (--effort <= 0) {
return;
}
if (si == s.length()) {
string t;
for (int j = 0; j < thisSltn.size(); j++) {
t += wordDict[thisSltn[j]] + " ";
}
allSltn.push_back(t.substr(0, t.length()-1));
effort += 100;
return;
}
for (int w = 0; w < wordDict.size(); ++w) {
if (wordDict[w].length() <= s.length() - si)   {
if (s.substr(si, wordDict[w].length()) ==  wordDict[w]) {
thisSltn.push_back(w);
helper(s, wordDict, int(si+wordDict[w].length()), thisSltn, allSltn);
thisSltn.pop_back();
}
}
}
}

vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> sltn(0);
vector<int> t(0);
effort = 100;
helper(s, wordDict, 0, t, sltn);

return sltn;
}
};

• consider this case:

string = str1 + "ba", str1 = "aa...a"
wordDict = ["a", "aa", "aaa", "aaaa", .., str1, str1+"ba"]

There is only one solution, but dfs will get TLE.

I think just check whether string is breakable is not sufficient, you should do some preprocessing (e.g. check at index k whether s[k : end] is breakable).

• If the DFS (exponential) is sufficiently long - for example the hypothetical example with 'b' at the end - then the only non-TLE approach is memoisation of the result space. That approach could work quick enough, but then the the space usage becomes exponential.

Ultimately the solution is exponential - time or space. Pick one.

• To avoid TLE, just as @liji94188 suggested, call WordBreak 1 first to check whether it is breakable. Here is my Javascript implementation using bottom-up DP. It seems all the other solutions are using cached recursive function call, essentially top-down DP.

var wordBreak = function(s, wordDict) {
var n = wordDict.length;
var len = s.length;
if (n == 0) return [];
if (s.length == 0) return [];
var dict = {};
var maxWLen = 0;
for (var i=0; i<n; i++) {
dict[wordDict[i]] = true;
maxWLen = Math.max(maxWLen, wordDict[i].length);
}

var map = new Array(len).fill(false);

// 1st DP is WordBreak 1.Tells whether the word is breakable.
for (var i=0; i<len; i++) {
for (var j=i; j>=0;j--) {
var str = s.substring(j,i+1);
if (dict[str]){
if (j == 0) {
map[i] = true; break;
} else if (map[j-1]) {
map[i] = true; break;
}
}
}
}

// early return if not breakable.
if (!map[len-1]) return [];

// 2nd DP constructs result.
for (var i=0; i<len; i++) {
map[i] = [];
}
for (var i=0; i<len; i++) {
for (var j=i; j>=0 && (i+1 -j) <= maxWLen; j--) {
var tail = s.substring(j, i+1);
if (dict[tail]) {
if (j == 0) map[i].push(tail);
else if( map[j-1].length > 0) {
for (var k=0; k<map[j-1].length; k++) {
map[i].push(map[j-1][k] + ' ' + tail);
}
}
}
}
}
return map[len-1];
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.