Word Break

Problem Statement

Given a string and a dictionary, can you segment the string into space-separated words from the dictionary? This medium-level DP riddle is a linguist’s playground—break it down!

Example

Input: s = "leetcode", wordDict = ["leet", "code"]

Output: true ("leet code")

Input: s = "applepenapple", wordDict = ["apple", "pen"]

Output: true ("apple pen apple")

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: false

Code

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        Set dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
            

def word_break(s, wordDict):
    word_set = 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 word_set:
                dp[i] = True
                break
    return dp[len(s)]
            

function wordBreak(s, wordDict) {
    let dict = new Set(wordDict);
    let dp = new Array(s.length + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && dict.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];
}
            

Explanation

• DP Insight: dp[i] = true if substring[0:i] can be segmented.
• Flow: Check all prefixes that form words with dict.
• Example: "leetcode" → dp[8]=true ("leet"+"code").

Note