Word Break

medium Dynamic Programming

Given a string s and a list of strings wordDict representing a dictionary, return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same dictionary word may be reused multiple times in the segmentation.

Example

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

Output: true

The string can be segmented as "leet" + "code", and both words are in the dictionary.

dp[i] answers whether s[0:i] can be segmented into dictionary words. For each position i, check every earlier position j: if dp[j] is true and the substring s[j:i] exists in the dictionary, then dp[i] is true. This builds up from the empty string (dp[0] = true) to the full string.

Why this works

Instead of trying every possible way to split the string (exponential), you build up answers left to right. If you know that the first j characters can be split into valid words, and the substring from j to i is also a dictionary word, then the first i characters can be split too. This avoids re-solving the same sub-problems.

Step by step

Convert to a set — put all dictionary words in a hash set for O(1) membership checks.
Set up the DP array — dp[i] means “can s[0:i] be segmented?” Start with dp[0] = true (empty string).
Try every split point — for each position i, try every earlier position j. If dp[j] is true and s[j:i] is a dictionary word, set dp[i] = true.
Return dp[n] — this tells you whether the entire string can be segmented.

Time: O(n²·k) Space: O(n)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict); // O(1) lookups
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // empty string is always segmentable
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) { // s[0:j] valid AND s[j:i] is a word
                    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()); // O(1) lookups
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true; // empty string is always segmentable
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.count(s.substr(j, i - j))) { // s[0:j] valid AND s[j:i] is a word
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

def wordBreak(s: str, wordDict: list[str]) -> bool:
    word_set = set(wordDict)  # O(1) lookups instead of scanning the list
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string is always segmentable
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:  # s[0:j] is valid AND s[j:i] is a word
                dp[i] = True
                break
    return dp[n]