Word Break - Python Solution

1. Introduction

"Word Break" is a classic problem that combines elements of dynamic programming, string manipulation, and set theory. The challenge lies in determining if a given string can be segmented into a sequence of words that are present in a given dictionary. This problem is commonly seen in coding interviews and is crucial for understanding how to approach string-based puzzles using dynamic programming.

Problem

Given a string s and a dictionary of strings wordDict, the objective is to return true if s can be segmented into a space-separated sequence of one or more dictionary words. It's important to note that the same word in the dictionary may be reused multiple times in the segmentation.

2. Solution Steps

1. Use dynamic programming to keep track of substring solutions.

2. Initialize a boolean array dp with a length of s.length() + 1, where dp[i] indicates whether the first i characters of s can be segmented.

3. Set dp[0] to true as the base case.

4. Iterate over the string s and for each index, check all possible substrings that end at that index.

5. If a valid substring is found and its remaining part also forms valid words (as per dp), mark the current position in dp as true.

6. Continue this process until the end of the string is reached.

3. Code Program

def wordBreak(s, wordDict):
    wordSet = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break

    return dp[len(s)]

# Example Usage
print(wordBreak("leetcode", ["leet", "code"]))
print(wordBreak("applepenapple", ["apple", "pen"]))
print(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))

Output:

True
True
False

Explanation:

1. Dynamic Programming Array: dp is used to store boolean values indicating whether a substring can be formed from words in wordDict.

2. Substring Checks: The algorithm iterates through the string and checks for every possible substring.

3. Dictionary Lookup: For each substring, it checks if the substring exists in the wordSet.

4. Updating dp: If a valid word is found, dp[i] is marked true, indicating that the substring ending at index i is valid.

5. Iterative Process: This process repeats, building up the solution for the entire string.

6. Final Result: The value at dp[len(s)] tells whether the entire string can be segmented into dictionary words.