Blind 75 Visualized

#57 · 1D DP

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 (words may be reused).

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Boolean DP over positions

dp[i] says whether the suffix of s starting at position i can be segmented. dp[n] is true (nothing left). A position is segmentable if some word fits at i and the position right after that word is segmentable.

Memory layout

A flat array of n + 1 booleans.

OperationCost
timeO(n · m · L) with word matching, or O(n · maxLen · L) with a set
spaceO(n)

Hash set of words

A set turns "is this piece a dictionary word?" into one hash lookup. Combined with the longest word length it limits how many pieces are examined.

Memory layout

A hash table of strings, plus one integer for the longest length.

OperationCost
membershipO(piece length)

Why it fits

  • Whether the tail of the string can be segmented does not depend on how the front was cut, only on where the tail starts. That makes position the whole state of the problem.
  • There are only n + 1 positions, so remembering each answer (especially the failures) removes the exponential blow-up of trying every cutting.
  • Words have a bounded length, so from each position only a few cut points can ever matter.

Why alternatives degrade

Greedy: always take the longest matching word:
For s = "abcd" with words ab, abc, cd, taking the longest match first uses "abc" and is stuck with "d", while the valid cutting is ab + cd.
Plain recursion:
Every way of cutting the prefix reaches the same suffix again, so work is repeated exponentially.
Regular expression (word1|word2)+:
It works for small dictionaries but backtracks exponentially on inputs like "aaaa…ab".

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(m^n) in the worst casespace O(n)

can(i) tries every dictionary word that matches the text at position i and recursively checks the remainder. It is true as soon as one choice works, and true at the end of the string.

bool wordBreak(string s, vector<string>& wordDict) {
    function<bool(int)> can = [&](int i) -> bool {
        if (i == (int)s.size()) return true;
        for (const string& word : wordDict) {
            if (s.compare(i, word.size(), word) == 0 && can(i + word.size())) return true;
        }
        return false;
    };
    return can(0);
}

Flaws & bottlenecks

  • The same suffix is explored again and again by different cuttings.
  • Strings like "aaaa…ab" with words a, aa, aaa take exponential time.
  • Tests every dictionary word at every position, even long words that cannot fit.

Interviewer cross-questions

Why is it exponential?

Say: There are many ways to cut the same prefix (a, aa, aaa pieces) and each ends in the same hopeless suffix. Nothing remembers that the suffix already failed.

How would you add memory?

Say: Store the result of can(i) for every position, including false results, so each position is searched at most once.

Does startsWith(word, i) copy the substring?

Say: Not in most implementations; it compares in place. Slicing a substring, as other approaches do, allocates a new string.

2 · intermediate

Memoised recursion

time O(n · m · L)space O(n)

Same recursion, but each position's result (true or false) is stored in a memo array. A repeated call returns immediately.

bool wordBreak(string s, vector<string>& wordDict) {
    vector<int> memo(s.size() + 1, -1);
    function<bool(int)> can = [&](int i) -> bool {
        if (i == (int)s.size()) return true;
        if (memo[i] != -1) return memo[i];
        bool ok = false;
        for (const string& word : wordDict) {
            if (s.compare(i, word.size(), word) == 0 && can(i + word.size())) {
                ok = true;
                break;
            }
        }
        memo[i] = ok;
        return ok;
    };
    return can(0);
}

Flaws & bottlenecks

  • Still recursive: depth up to n.
  • A tri-state memo (unknown, true, false) is needed; a plain boolean array cannot tell "false" from "not computed".
  • Every call loops over the whole dictionary.

Interviewer cross-questions

Why must false results be stored too?

Say: The exponential cost comes from re-discovering failures. If only successes were stored, a failing suffix would be re-searched every time it was reached.

What is the complexity now?

Say: There are n + 1 positions, each tries m words with an O(L) comparison: O(n · m · L).

How would you avoid recursion?

Say: Fill an array from the end of the string backwards, as the table approach does.

3 · advanced

Bottom-up table over cut points

time O(n² · L)space O(n + total dictionary size)

dp[i] is true if some piece s[i..j) is in the dictionary set and dp[j] is true. Fill i from the end to the start, trying every j, with dp[n] = true.

bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.size();
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    vector<bool> dp(n + 1, false);
    dp[n] = true;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j <= n; j++) {
            if (dp[j] && words.count(s.substr(i, j - i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[0];
}

Flaws & bottlenecks

  • Tries every cut point up to the end of the string, even where no word could be that long.
  • Each slice allocates a string whose hash costs O(length).
  • Checking dp[j] first avoids slicing when the rest is hopeless, but the loop still runs.

Interviewer cross-questions

Why check dp[j] before slicing?

Say: If the rest from j cannot be segmented, the piece does not matter, so the slice and hash can be skipped.

Why iterate from the right?

Say: dp[i] depends on dp[j] for j > i. Going from n − 1 down to 0 makes all of them final when needed.

How can the cut points be limited?

Say: No word is longer than the longest dictionary word, so only j up to i + maxLen need to be tried.

4 · expert

Table with a cap on piece length

time O(n · maxLen · L)space O(n + total dictionary size)

Compute the length of the longest dictionary word and try only cut points within that distance. Each position then does O(maxLen) lookups, so the cost is O(n · maxLen) lookups rather than O(n²).

bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.size();
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int maxLen = 0;
    for (const string& w : wordDict) maxLen = max(maxLen, (int)w.size());
    vector<bool> dp(n + 1, false);
    dp[n] = true;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j <= min(n, i + maxLen); j++) {
            if (dp[j] && words.count(s.substr(i, j - i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[0];
}

Flaws & bottlenecks

  • One extra pass over the dictionary to find the longest word.
  • If one word is huge the cap does little (a dictionary with a word as long as s is back to quadratic).
  • Slices still allocate; a trie would avoid creating strings at all.

Interviewer cross-questions

Why is capping the cut length safe?

Say: A piece longer than every dictionary word cannot be in the dictionary, so trying it can never succeed.

How would a trie help?

Say: Walk the trie letter by letter from position i: each step extends the piece by one letter and stops as soon as no word has that prefix. No substring is ever created and the walk ends at the first dead prefix.

How do you handle a very large dictionary?

Say: Build the set (or trie) once, keep only the lengths that occur (a bitmask of word lengths), and for each position try only those lengths.

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

bool wordBreak(string s, vector<string>& wordDict) {
    function<bool(int)> can = [&](int i) -> bool {
        if (i == (int)s.size()) return true;
        for (const string& word : wordDict) {
            if (s.compare(i, word.size(), word) == 0 && can(i + word.size())) return true;
        }
        return false;
    };
    return can(0);
}