Word Break

Medium Problem 121 of 151 Java and Python

Problem

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. A word may be reused.

Example 1

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

Example 2

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Why: "apple" is reused.

Example 3

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

Constraints

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000, 1 ≤ wordDict[i].length ≤ 20

Explanation

Let dp[i] mean "the first i characters can be split". dp[i] is true if some earlier dp[j] is true and s[j..i) is a dictionary word.

Plain recursion tries the same suffixes again and again; the table computes each prefix once.

Approach 1 · Naive

Recursion over prefixes

Time O(2ⁿ) worst case
Space O(n) recursion

Try every dictionary word that is a prefix of s, and recurse on the rest.

If s is empty, return true.
For each word that s starts with, return true if the remainder can be broken.

Java

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s.isEmpty()) {
            return true;
        }
        for (String word : wordDict) {
            if (s.startsWith(word) && wordBreak(s.substring(word.length()), wordDict)) {
                return true;
            }
        }
        return false;
    }
}

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s:
            return True
        return any(s.startswith(w) and self.wordBreak(s[len(w):], wordDict) for w in wordDict)

Approach 2 · Optimal

Bottom-up DP over prefixes

Time O(n² · L) for the substring checks
Space O(n + dictionary)

Fill dp[0..n]; dp[i] is true when a dictionary word ends at i and starts at a reachable j.

Put the words in a set; dp[0] = true.
For each i from 1 to n, for each j < i: if dp[j] and s[j..i) is in the set, set dp[i] = true and stop.
Return dp[n].

Java

import java.util.*;

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

Python

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

Complexity compared

Approach	Time	Space
Naive Recursion over prefixes	O(2ⁿ) worst case	O(n) recursion
Optimal Bottom-up DP over prefixes	O(n² · L) for the substring checks	O(n + dictionary)

Key takeaways

Limit j to the last maxWordLength positions to speed it up on long strings.
Word Break II (list all sentences) adds backtracking on top of this table.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem