Command Palette

Search for a command to run...

Hectal
Problem 28.7 · DP Foundations: 1DMedium

Word Break

Pattern1D Dynamic ProgrammingHash Map Lookup (Complement)Trie (Prefix Tree)

What it teaches: A yes/no DP over prefixes: can the first i characters be split into dictionary words?

Practise it on judges as “Word Break”.

The problem

Return true if s can be split into a sequence of one or more dictionary words (words may be reused).

Example 1

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

Example 2

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

Constraints

  • 1 ≤ s.length ≤ 300
  • Word length ≤ 20

Pattern clues in the wording

  • → Split a string into valid pieces

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "leetcode"
wordDict = ["leet","code"]
true
2
s = "applepenapple"
wordDict = ["apple","pen"]
true
3
s = "catsandog"
wordDict = ["cats","dog","sand","and","cat"]
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Prefix DP with a word set · O(n × L²) with L the longest word
1

Prefix DP with a word set

Time O(n × L²) with L the longest word Space O(n + dictionary)

ok[0] = true. For each end i, try start j within the maximum word length.

Approach 1
import java.util.*;

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());
        boolean[] ok = new boolean[s.length() + 1];
        ok[0] = true;
        for (int i = 1; i <= s.length(); i++)
            for (int j = Math.max(0, i - maxLen); j < i && !ok[i]; j++)
                if (ok[j] && words.contains(s.substring(j, i))) ok[i] = true;
        return ok[s.length()];
    }
}

Verdict: Limiting j by word length keeps it fast.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Word reused many times
  • No word fits the end

Mistakes people make

  • Greedily taking the longest matching word (fails on "aaaaaaa" with [aaaa, aaa]).

Interview

Follow-up questions

How do you list all sentences (Word Break II)?