Implement the wordBreakPossible method that checks whether the text can be segmented using the given dictionary words.
The input contains a string text, an array of dictionary words words, and the number of words size. Your task is to check whether the complete string can be split into one or more dictionary words.
Each dictionary word may be used multiple times if needed. 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 mark which prefixes of the string can be formed using the dictionary.
Let dp[i] mean that the first i characters of text can be segmented correctly. Start with dp[0] = true because an empty prefix is valid.
For every ending position, check earlier split positions. If the part before the split is valid and the substring after the split exists in the dictionary, mark the current position as valid.
Pseudocode:
function wordBreakPossible(text, words, size):
dictionary = set containing all words
n = length(text)
dp = boolean array of n + 1 values filled with false
dp[0] = true
for end from 1 to n:
for start from 0 to end - 1:
currentWord = substring of text from start to end - 1
if dp[start] == true and currentWord is in dictionary:
dp[end] = true
break
return dp[n]