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