Problem Description

The Word Break problem asks you to determine if a given string s can be segmented into a space-separated sequence of one or more words that are all present in a given dictionary wordDict.

• You may use each word in wordDict as many times as needed.
• All words in wordDict are non-empty and there are no duplicate words.
• Return true if s can be segmented as described, or false otherwise.
• The dictionary may not be sorted, and words can be of varying lengths.

Example:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true (since "leetcode" can be split as "leet code")

Thought Process

At first glance, the problem seems to ask whether we can split the string s into chunks that all exist in wordDict. A brute-force approach would be to try every possible way to split the string and check if each chunk is in the dictionary. However, this quickly becomes infeasible for long strings due to the exponential number of ways to split a string.

To optimize, we need to avoid recalculating the same subproblems. This is a classic scenario for Dynamic Programming (DP). By storing results of previously solved subproblems, we can efficiently build up to the solution for the full string.

The core insight is: for each position in the string, check if there is a previous split such that the substring after that split is a dictionary word and the prefix up to that split can be segmented.

Solution Approach

We use a bottom-up dynamic programming approach to solve this efficiently:

1. DP Array: Create a boolean array dp of size len(s) + 1. dp[i] is true if s[0:i] can be segmented using words from wordDict.
2. Initialization: Set dp[0] = true because the empty string can always be segmented.
3. Dictionary Lookup: To speed up word lookups, convert wordDict to a set (hash set) for O(1) lookup time.
4. Filling DP: For each position i from 1 to len(s):
   • For each j from 0 to i:
   • If dp[j] is true and s[j:i] is in the dictionary, set dp[i] = true and break inner loop (no need to check further splits).
5. Result: The answer is dp[len(s)].

This approach avoids recomputation and ensures we only check necessary splits.

Example Walkthrough

Let's walk through an example with s = "applepenapple" and wordDict = ["apple", "pen"].

1. Initialization: dp[0] = true. All other dp[i] are false.
2. i = 5: s[0:5] = "apple" is in the dictionary and dp[0] is true, so dp[5] = true.
3. i = 8: s[5:8] = "pen" is in the dictionary and dp[5] is true, so dp[8] = true.
4. i = 13: s[8:13] = "apple" is in the dictionary and dp[8] is true, so dp[13] = true.
5. Final check: dp[13] is true, so the string can be segmented.

At each step, we only mark dp[i] as true if a valid word ends there and the prefix is segmentable.

Time and Space Complexity

Brute-force: The naive recursive approach tries every possible split, resulting in exponential time complexity: O(2^n), where n is the length of s.

Optimized DP:

• Time: For each position i, we check all possible previous splits j, so it's O(n^2). Dictionary lookups are O(1) due to the hash set.
• Space: O(n) for the DP array and O(mk) for the dictionary, where m is the number of words and k is the average word length.

Summary

The Word Break problem is elegantly solved using dynamic programming by building up solutions to smaller substrings and storing these results for reuse. By leveraging a DP array and a hash set for fast lookups, we avoid redundant work and achieve an efficient O(n^2) solution. The key insight is that a string can be segmented if any prefix can be segmented and the remaining substring is a dictionary word.

Code Implementation

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

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

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};
      

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
      

var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
};