Implement the wordBreakDpPossible method that checks whether dynamic programming can segment the text into dictionary words.
The input contains a string text, an array words, and the number of words size. The array represents a dictionary of valid words.
Your task is to check whether the complete string can be split into one or more dictionary words. The same dictionary word may be used more than once.
For example, leetcode can be split as leet + code, so the answer is true.
Example 1
leetcode[leet,code]2trueExample 2
applepenapple[apple,pen]2trueExample 3
catsandog[cats,dog,sand,and,cat]5falseUse dynamic programming to check which prefixes of the string can be formed using dictionary words.
Let dp[i] mean that the first i characters of text can be split successfully. Start with dp[0] = true because an empty prefix is always valid.
For every end position, check earlier split positions. If the left part is already valid and the substring from that split to the end is present in the dictionary, mark the current position as valid.
Pseudocode:
function wordBreakDpPossible(text, words, size):
dictionary = set of words
n = length of text
create boolean array dp of size n + 1 with false values
dp[0] = true
for end from 1 to n:
for start from 0 to end - 1:
part = substring text from start to end
if dp[start] == true and part exists in dictionary:
dp[end] = true
break
return dp[n]