The dynamic programming approach could be based on the following recursive formula:
f(n) = true
f(i) = OR { d(s[i]s[i+1]...s[j-1]) AND f(j) | for each j such that i < j <= n }
Start from f(0).
Explanation:
If you got to the end of the string - you're good (base clause).
Otherwise, try to split the word wherever you can from the given start (which is i
), and recursively invoke on the suffix of the string.
Complexity is actually O(n^2 * g(n))
where g(n)
is the time it takes for dict
to check if the word is in it. (Every solution need to depend on it somehow...)
Converting to DP solution:
Fill the table from last to first, according to the logic described in the recursive formula.