Problem statement

Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words (words may be reused).

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 8
• 1 <= wordDict[i].length <= 5
• Lowercase letters; dictionary words are distinct.

Hints for Word Break

1. Hint 1

   dp[i]: can the prefix of length i be segmented?

2. Hint 2

   dp[i] is true if some j < i has dp[j] true and s[j..i) in the dictionary.

How to solve Word Break

Let ok[i] mean "the first i characters can be segmented". The prefix of length i is segmentable when some dictionary word w ends exactly at i and the prefix before it, of length i - |w|, is itself segmentable. Build the flags left to right and every lookup is already resolved.

Approach

1. Set ok[0] = true — the empty prefix is trivially segmentable.
2. For each length i from 1 to |s|, try every dictionary word w.
3. If |w| <= i, ok[i - |w|] is true, and s matches w at position i - |w|, then mark ok[i] and stop trying words for this i.
4. Return ok[|s|].

Why it works

Any segmentation has a unique final word, so splitting on that word covers every possibility without overlap — and the part before it must itself be a valid segmentation, which is the optimal-substructure property. Memoising the flags is what avoids the exponential blow-up of plain recursion: the same prefix would otherwise be re-explored once for every path that reaches it.

Complexity

• Time — O(|s| · |dict| · maxWordLength)
• Space — O(|s|)

Pitfalls

• ok[0] = true is the seed; without it nothing is ever reachable.
• Words may be reused any number of times, so there is no bookkeeping of which words were consumed.
• Check ok[i - |w|] before the string comparison — a matching word after an unreachable prefix proves nothing.
• Greedily taking the longest matching word fails: "catsandog" with ["cats","cat","sand","and","dog"] needs the shorter "cat" first.

Reference solution

Python

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> bool:
    words = set(wordDict)
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

Java

public static boolean wordBreak(String s, String[] wordDict) {
    int n = s.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (String w : wordDict) {
            int L = w.length();
            if (L <= i && ok[i - L] && s.substring(i - L, i).equals(w)) {
                ok[i] = true;
                break;
            }
        }
    }
    return ok[n];
}

C++

bool wordBreak(string s, vector<string>& wordDict) {
    int n = (int) s.size();
    vector<bool> ok(n + 1, false);
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (const string& w : wordDict) {
            int L = (int) w.size();
            if (L <= i && ok[i - L] && s.compare(i - L, L, w) == 0) {
                ok[i] = true;
                break;
            }
        }
    }
    return ok[n];
}

JavaScript

var wordBreak = function(s, wordDict) {
    const words = new Set(wordDict);
    const 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] && words.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium