Start practising

Word Break

Medium Dynamic Programming 1D DP Original on LeetCode

Word Break is a medium dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (1d dp over prefixes), runs in O(n · L²) time and O(n) space. Below are 2 approaches in Java, from recursion up.

Problem

Given a string s and a dictionary of words, decide whether s can be split into a sequence of one or more dictionary words. Words may be reused.

Examples

Example 1

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

Example 2

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

Constraints

  • 1 <= s.length <= 300; up to 1000 words of length 1 to 20.
  • Dictionary words may be reused.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
RecursionO(2ⁿ)O(n)
Optimal (1D DP over prefixes)O(n · L²)O(n)

1Recursion

TimeO(2ⁿ)
SpaceO(n)

Try every dictionary word as a prefix and recurse on the rest.

  1. If start == n return true.
  2. For each end: if s[start..end) is a word and rec(end), return true.
Java
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return can(s, 0, new HashSet<>(wordDict));
    }

    private boolean can(String s, int start, Set<String> dict) {
        if (start == s.length()) return true;
        for (int end = start + 1; end <= s.length(); end++)
            if (dict.contains(s.substring(start, end)) && can(s, end, dict)) return true;
        return false;
    }
}

2Optimal (1D DP over prefixes)

TimeO(n · L²)L = longest word; each check builds a substring of length up to L.
SpaceO(n)

dp[0] = true. For each i, look back at split points j: if dp[j] is true and s[j..i) is in the set, dp[i] is true. Limiting j to the longest word length keeps it fast.

  1. dict = set; maxLen = longest word.
  2. For i in 1..n, for j from i - 1 down to max(0, i - maxLen): if dp[j] && dict has s[j..i), dp[i] = true; break.
Java
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = i - 1; j >= Math.max(0, i - maxLen); j--)
                if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
        return dp[n];
    }
}

Edge cases to test

  • Reusing the same word several times
  • Many prefixes match but the suffix fails

Hints

Hint 1

dp[i] = can the first i characters be segmented? dp[i] is true if some dp[j] is true and s[j..i) is a word.

FAQ

What is the best time complexity for Word Break?

Optimal (1D DP over prefixes) runs in O(n · L²) time and O(n) extra space. L = longest word; each check builds a substring of length up to L.

Which pattern does Word Break use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Word Break?

Yes. Recursion takes O(2ⁿ) time and O(n) space. Try every dictionary word as a prefix and recurse on the rest.

Which edge cases should I test for Word Break?

Reusing the same word several times; Many prefixes match but the suffix fails.