Please add test case 'baaaaaaaa...aaaa', ['a', 'aa', 'aaa', ..., 'aaa...aa']

  • 24

    The topic has been well discussed in many posts such as here and here. Because the existence of test case 'aaaaa...aaaab', ['a', 'aa', 'aaa', ... 'aaa...aa'], the forward DP solution will cause MLE while the backward DP is just fine, apparently the test case 'baaaaaaaa...aaaa', ['a', 'aa', 'aaa', ..., 'aaa...aa'] should also be included.

  • 0

    Hi, my understanding about this problem is that once we know dp[i], representing whether s[0...i] is re-constructable, we will stop at the first step for both case baaaaaaaa...aaaa and aaaaa...aaaab, since dp[s.length()] = false.

    If we add 'b' into the dictionary, it is the same case as 'aaaaa...aaaa', ['a', 'aa', 'aaa', ... 'aaa...aa']

    Back-tracing from the tail benefits because it is ensured that every path we generated is a valid path as long as your dp[] =true/false array is correct.

  • 1

    Thanks so much for pointing this out. I have added the test case so both mentioned solutions get Time Limit Exceeded now. Thanks!

Log in to reply

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