Word Break

Given a string s and a dictionary of words, return true if s can be split into a sequence of one or more dictionary words. A word may be used any number of times.

LeetCode: 139. Word Break

Example

s = "applepenapple",  dict = ["apple", "pen"]                        ->  true   (apple pen apple)
s = "catsandog",      dict = ["cats", "dog", "sand", "and", "cat"]   ->  false

In "catsandog", both "cat" + "sand" and "cats" + "and" get as far as "og", which can't be split.

Brute force: try every first word

If some prefix of s is a dictionary word, and the rest can be split, then s can be split.

canSplit(s, start, dict) checks the suffix of s that begins at index start. s.substring(a, b) returns the characters from a up to but not including b.

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

public class Main {
    static boolean canSplit(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)) && canSplit(s, end, dict)) return true;
        }
        return false;
    }

    static boolean wordBreak(String s, List<String> words) {
        return canSplit(s, 0, new HashSet<>(words));
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("applepenapple", List.of("apple", "pen")));
        System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
    }
}

true
false

Time: O(2ⁿ) in the worst case. For s = "aaaa...ab" with dict = ["a", "aa", "aaa"], every way of splitting the as is explored before failing at b. Space: O(n) for the recursion.

Optimal: DP over prefixes

The recursion only ever asks one question: can the suffix starting at some position be split? There are only n + 1 positions. Turn it around and work on prefixes: let can[i] be true if the first i characters of s can be split.

can[0] = true                                   (the empty prefix)
can[i] = true if some j < i has can[j] and s[j..i] in the dictionary

For "applepenapple": can[5] ("apple"), can[8] (can[5] and "pen"), and can[13] (can[8] and "apple").

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

public class Main {
    static boolean wordBreak(String s, List<String> words) {
        Set<String> dict = new HashSet<>(words);
        int maxLen = 0;
        for (String w : words) maxLen = Math.max(maxLen, w.length());
        int n = s.length();
        boolean[] can = new boolean[n + 1];
        can[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                if (can[j] && dict.contains(s.substring(j, i))) {
                    can[i] = true;
                    break;
                }
            }
        }
        return can[n];
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("applepenapple", List.of("apple", "pen")));
        System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
        String longInput = "a".repeat(100) + "b";
        System.out.println(wordBreak(longInput, List.of("a", "aa", "aaa")) + " " + wordBreak("", List.of("x")));
    }
}

true
false
false true

Time: O(n · L · L) for words up to length L: for each end i, at most L start positions, each hashing a substring of up to L characters. Space: O(n) plus the dictionary.

Only the last max_len positions can start a dictionary word that ends at i, which is why j begins at i - maxLen (clamped to 0). Without that bound, the loop is O(n²) substring lookups. substring copies its characters, which is the O(L) cost counted above. It indexes 16-bit char units, which is correct for the lowercase ASCII input the problem uses.

A trie of the dictionary replaces the hashing: from each j with can[j], walk the trie along the characters of s from j and mark every position where a word ends.

Edge cases

• Empty string: true, since can[0] is true (LeetCode guarantees s is non-empty).
• Characters that appear in no word: every can[i] past that character is false.
• Listing every split (LeetCode 140): backtrack over the same choices, skipping positions where the rest can't be split.