Solution: Word Break
Go Back

## Problem Statement

Given a non-empty string and a dictionary containing a list of non-empty words, determine if the string can be segmented into a space-separated sequence of one or more dictionary words. Each word in the dictionary can be reused multiple times.

### Examples

Example 1:

• Input:
• String: "ilovecoding"
• Dictionary: ["i", "love", "coding"]
• Expected Output: True
• Justification: The string can be segmented as "i love coding".

Example 2:

• Input:
• String: "helloworld"
• Dictionary: ["hello", "world", "hell", "low"]
• Expected Output: True
• Justification: The string can be segmented as "hello world".

Example 3:

• Input:
• String: "enjoylife"
• Dictionary: ["enj", "life", "joy"]
• Expected Output: False
• Justification: Despite having the words "enj" and "life" in the dictionary, we can't segment the string into the space-separated dictionary words.

Constraints:

• `1 <= s.length <= 300`
• `1 <= wordDict.length <= 1000`
• `1 <= wordDict[i].length <= 20`
• `s` and `wordDict[i]` consist of only lowercase English letters.
• All the strings of wordDict are unique.

## Solution

Our algorithm's primary objective is to determine whether the given string can be broken down into a sequence of words present in the dictionary. To achieve this, we use a dynamic programming approach, maintaining an array to keep track of the possibility of forming valid sequences up to every index of the string. The primary idea is to iterate through the string and, at each step, check all possible word endings at the current position. If a valid word is found, and the starting position of that word was marked as achievable, we mark the current position as achievable too.

1. Initialization:

• Begin by initializing a boolean array `dp` of size `n+1`, where `n` is the length of the string. This array will record whether the string can be segmented up to a certain index. We set the first element, `dp[0]`, to `true` since an empty string can always be segmented.
2. Dynamic Programming:

• Iterate over the length of the string. For each index `i`, verify every substring ending at `i` and see if it exists in the dictionary.
• If a valid word is found and the starting position (denoted as `dp[j]`) of the substring is true, set `dp[i+1]` to true.
• Proceed in this manner until you reach the end of the string.
3. Result:

• Once the iteration is complete, the value of `dp[n]` will indicate if the entire string can be segmented into dictionary words or not.
4. Optimization:

• For faster lookups, convert the word dictionary into a set. This ensures constant time complexity when searching for words in the dictionary.

### Algorithm Walkthrough

Given the string "helloworld" and dictionary ["hello", "world", "hell", "low"]:

• Initialize `dp` to `[true, false, false, ..., false]` (length = 11 since "helloworld" has 10 characters).
• For `i = 0`, substring = "h". It's not in the dictionary, so move to next.
• For `i = 1`, substring = "he", "h". Neither is in the dictionary.
• For `i = 4`, substring = "hello", which is in the dictionary and `dp[0]` is true. So, set `dp[5]` to true.
• Continuing this, when we get to `i = 9`, substring = "world" is in the dictionary, and `dp[5]` is true, so we set `dp[10]` to true.
• Finally, `dp[10]` is true, so "helloworld" can be segmented.

Python3
Python3

## Complexity Analysis

• Time Complexity: O(n^2) due to the two nested loops where we check all possible substrings.
• Space Complexity: O(n) for the DP array and the word set.