Word Break

NeetCode: Word Break · LeetCode: 139. Word Break · Difficulty: Medium

Given a string s and a list of words wordDict, return true if s can be split into a sequence of dictionary words. Words may be reused.

Example

Text

Input:  s = "leetcode", wordDict = ["leet", "code"]                         Output: true
Input:  s = "applepenapple", wordDict = ["apple", "pen"]                    Output: true
Input:  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]   Output: false

Brute force: recursion over the split point

can(start) answers whether s.substring(start) breaks into words. Try every end e; if s.substring(start, e) is a word and can(e) holds, the answer is true. Reaching the end of the string succeeds.

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    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;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        return can(s, 0, new HashSet<>(wordDict));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wordBreak("leetcode", List.of("leet", "code")));
        System.out.println(sol.wordBreak("applepenapple", List.of("apple", "pen")));
        System.out.println(sol.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
        System.out.println(sol.wordBreak("", List.of("a")));
    }
}

Output

true
true
false
true

On inputs like "aaaa...ab" with words a, aa, aaa, the same suffixes fail repeatedly through many different splits. Time: O(2^n) in the worst case. Space: O(n) stack.

Better: memoization

Whether the suffix s.substring(start) is breakable depends only on start. Caching it means each of the n suffixes is solved once. The memo is a byte[] with three states (not computed, true, false), because a plain boolean[] cannot tell "false" from "not computed". substring copies its characters, so each call costs time proportional to the substring length.

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    // memo[start]: 0 = not computed, 1 = true, 2 = false
    private boolean can(String s, int start, Set<String> dict, byte[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != 0) {
            return memo[start] == 1;
        }
        boolean ok = false;
        for (int end = start + 1; end <= s.length() && !ok; end++) {
            ok = dict.contains(s.substring(start, end)) && can(s, end, dict, memo);
        }
        memo[start] = (byte) (ok ? 1 : 2);
        return ok;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        return can(s, 0, new HashSet<>(wordDict), new byte[s.length()]);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wordBreak("leetcode", List.of("leet", "code")));
        System.out.println(sol.wordBreak("applepenapple", List.of("apple", "pen")));
        System.out.println(sol.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
        System.out.println(sol.wordBreak("", List.of("a")));
    }
}

Output

true
true
false
true

Time: O(n^2) subproblem transitions, each hashing a substring of up to O(n) characters, so O(n^3) in the worst case. Space: O(n) plus the dictionary.

Optimal: bottom-up, bounded by the longest word

Let dp[i] mean "the first i characters can be broken into words", with dp[0] = true. For each i, look for a j < i with dp[j] true and s.substring(j, i) in the dictionary. A word is never longer than the longest dictionary word L, so only j >= i - L needs checking.

Java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

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 = Math.max(0, i - maxLen); j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wordBreak("leetcode", List.of("leet", "code")));
        System.out.println(sol.wordBreak("applepenapple", List.of("apple", "pen")));
        System.out.println(sol.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
        System.out.println(sol.wordBreak("", List.of("a")));
    }
}

Output

true
true
false
true

Time: O(n · L^2), where L is the longest word: n · L pairs (j, i), each hashing up to L characters (so at most O(n^3) if a word is as long as the string). Space: O(n + total dictionary size).