The easiest way to solve this is recursively with memoization. Note that there is a horrible test case that makes my iterative DP solution fail. That test case is not fair because those sorts of length strings will never work if they are valid as there are too many result permutations. So the memoization in the recursive solution is the thing to note. It doesn’t completely remove duplication of branches but it does remove duplication if there are no solutions in a branch. That is the key for solving the tricky test case because it has a b in the middle of all the a’s in s, which makes it impossible to match:
s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" wordDict=["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
