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

[ghost]

leetcode/src/wordBreak/wordBreak.II.cpp

Line 143 in 0858fdb

vector<string> wordBreak_dp(string s, set<string> &dict) {

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. 😉