String Dynamic Programming Memoization Tabulation
Proficient Level

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
Input:
text (string) = leetcode
words (string[]) = [leet,code]
size (int) = 2
Return:
(boolean) true
Example 2
Input:
text (string) = applepenapple
words (string[]) = [apple,pen]
size (int) = 2
Return:
(boolean) true
Example 3
Input:
text (string) = catsandog
words (string[]) = [cats,dog,sand,and,cat]
size (int) = 5
Return:
(boolean) false

Use 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]
Run your code to see the result.