Word Break Problem (LeetCode 139) – Description, Examples, and DP Solutions in Java and C++

LeetCode 139 – Word Break: Given a string s and a list of words wordDict , determine whether s can be segmented into a space‑separated sequence of one or more dictionary words.

Constraints: 1 ≤ s.length ≤ 300, 1 ≤ wordDict.length ≤ 1000, 1 ≤ wordDict[i].length ≤ 20, all strings consist of lowercase letters, and dictionary words are unique.

Example 1: Input: s = "leetcode", wordDict = ["leet","code"]; Output: true ("leetcode" = "leet" + "code").

Example 2: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]; Output: false.

Solution idea: use dynamic programming. Let dp[i] indicate whether the prefix s[0..i‑1] can be segmented. For each position i , check all previous cuts j (0 ≤ j < i); if dp[j] is true and s.substring(j,i) is in the dictionary, set dp[i]=true . The answer is dp[s.length] .

Java implementation:

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

C++ implementation:

bool wordBreak(string s, vector
& wordDict) {
    size_t len = s.size();
    vector
dp(len + 1, false);
    unordered_set
wordSet(wordDict.begin(), wordDict.end());
    dp[0] = true;
    for (size_t i = 1; i <= len; ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[len];
}