[Word Break II] Your code seems outdated and needs more test cases.

[ghost]

https://github.com/haoel/leetcode/blob/0858fdb3d9c4dba43135001e370a80ce518d5e82/src/wordBreak/wordBreak.II.cpp#L143

Your DP solution is not really efficient.

I can provide two test cases:

unordered_set<string> dict = {"a","aa","ab"};
string s = "babaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

unordered_set<string> dict = {"a","aa","ba"};
string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabab";

[haoel]

You are right, the DP is not efficient. Actually, the recursive solution is more efficient than that DP solution.

[yqtaowhu]

yes,i think the dp is not efficient , it will lead Memory Limit Exceeded, could you have any solution to solve it .

[ghost]

@yqtaowhu Sure, just visit the leetcode forum. 😉