# 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.

## Comments

## Post a Comment