Word Break

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given a string s and a list of distinct words wordDict. Return true if s can be split into a sequence of one or more pieces so that every piece is a word in wordDict, and false otherwise. The pieces must cover all of s, in order, with no characters skipped or left over. The same word may be used as many times as you like, and some words may go unused.

Examples

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

"leetcode" splits as "leet" + "code", and both are in the list.

s = "applepenapple", wordDict = ["apple","pen"] returns true

"apple" + "pen" + "apple" works, using "apple" twice.

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] returns false

Both "cats" + "and" and "cat" + "sand" cover "catsand", but the leftover "og" is not a word, and no other split reaches the end.

Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

Hints

Hint 1

If you know the first j characters can be split into words, what else must be true for the first i characters to be splittable?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Let ok[i] be true when the first i characters of s can be split into words, with ok[0] = true for the empty prefix. For each end i, try every cut j from i - 1 back to i - L (L = longest word length): if ok[j] is true and s[j:i] is in a hash set of the words, ok[i] is true. Return ok[n]. That's O(n * L^2) time, since each of the n * L checks hashes a substring of up to L characters, and O(n + m * L) space for m words.

Time

O(n * L^2)

Space

O(n + m * L)

Pitfall

Greedily taking the first word that fits. With s = "aaaaaaa" and wordDict = ["aaa","aaaa"], taking "aaa" twice strands the last "a", yet "aaa" + "aaaa" works, so you must track every reachable cut, not just one.

Solutions

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());

        int n = s.length();
        boolean[] ok = new boolean[n + 1]; // ok[i]: s[0..i) can be split into words
        ok[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= Math.max(0, i - maxLen); j--) {
                if (ok[j] && words.contains(s.substring(j, i))) {
                    ok[i] = true;
                    break;
                }
            }
        }
        return ok[n];
    }
}

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        max_len = max(len(w) for w in wordDict)

        n = len(s)
        ok = [False] * (n + 1)  # ok[i]: s[:i] can be split into words
        ok[0] = True
        for i in range(1, n + 1):
            for j in range(i - 1, max(0, i - max_len) - 1, -1):
                if ok[j] and s[j:i] in words:
                    ok[i] = True
                    break
        return ok[n]