Array String Dynamic Programming Memoization Tabulation
Proficient Level

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