MediumDynamic programming

Word Break

Q: Why strncmp instead of copying the piece and calling strcmp?

strncmp(s + start, word, len) compares in place and stops at the first difference, so most words are rejected after one character and nothing is allocated. It also stops at the NUL that ends s: if fewer than len characters remain, that NUL differs from the word's character and the result is non-zero, so no separate length check is needed.

Q: Why store the word lengths before recursing?

strlen walks the whole word every time it is called. The memo version checks up to 1,000 words at each of 300 starts, so measuring every word once into lens saves that walk on each of those checks. The lengths are also what tells the recursion where the next piece starts.

Q: How does bsearch find a piece that is not NUL-terminated?

The key is a Piece with a pointer into s and a length, and compare_piece compares the first len characters with strncmp. When they match, the piece equals the word only if the word ends right there (word[len] == 0); otherwise the word is longer and sorts after the piece. The array must be sorted with the same order, which strcmp in qsort gives.

Q: Why copy the words before qsort?

The caller owns words, and sorting it in place would change the order the caller sees after the call. Copying the pointers costs one malloc of wordsSize pointers; the strings themselves are shared, not duplicated.

You get a string s and an array of strings words, the dictionary. Return true if s can be cut into one or more pieces so that every piece is a word from words, read left to right with nothing left over, and false otherwise.

A word can be used any number of times, and not every word has to be used. Pieces cannot overlap: each character of s belongs to exactly one piece. An empty s needs no pieces, so the answer is true. All strings use lowercase letters a to z only, the words are distinct and none is empty.

Examples

Input

s = "paintpaintbrush"
words = ["brush", "paint", "pain", "rush"]

OutputtrueWhypaint + paint + brush covers the whole string, using paint twice.

Input

s = "starfishy"
words = ["star", "fish", "starfish", "shy"]

OutputfalseWhystar + fish and starfish both leave y, and shy would need starfi before it, which no words make.

Constraints

Size: 0 ≤ s.length ≤ 300
Dictionary: 1 ≤ words.length ≤ 1,000
Words: 1 ≤ words[i].length ≤ 20
Letters: Lowercase a to z only; the words are distinct; each word can be reused.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

can(s, words, start, memo) answers whether s from start onward splits into words. s.startsWith(w, start) checks a word in place without building a substring. The memo is a Boolean[], so null means "not solved yet" and each start is computed once.

import java.util.*;

public class Main {
    static boolean wordBreak(String s, String[] words) {
        return can(s, words, 0, new Boolean[s.length() + 1]);
    }

    static boolean can(String s, String[] words, int start, Boolean[] memo) {
        if (start == s.length()) return true;
        if (memo[start] != null) return memo[start];
        boolean result = false;
        for (String w : words) {
            if (s.startsWith(w, start) && can(s, words, start + w.length(), memo)) {
                result = true;
                break;
            }
        }
        memo[start] = result;
        return result;
    }
}

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

ok[i] is true when the first i characters split into words; a fresh boolean[] is all false, so only ok[0] needs setting. For each end, look back at most longest characters for a start with ok[start] set and s.substring(start, end) in the HashSet.

import java.util.*;

public class Main {
    static boolean wordBreak(String s, String[] words) {
        Set<String> vocab = new HashSet<>(Arrays.asList(words));
        int longest = 0;
        for (String w : words) longest = Math.max(longest, w.length());
        boolean[] ok = new boolean[s.length() + 1];
        ok[0] = true; // the empty prefix needs no words
        for (int end = 1; end <= s.length(); end++) {
            for (int start = Math.max(0, end - longest); start < end; start++) {
                if (ok[start] && vocab.contains(s.substring(start, end))) {
                    ok[end] = true;
                    break;
                }
            }
        }
        return ok[s.length()];
    }
}

2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

Can answers whether s from start onward splits into words. s.AsSpan(start).StartsWith(w) compares characters ordinally in place, with no substring and no culture rules. The memo is a bool?[], where null means not solved yet, so each start is computed once.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool WordBreak(string s, string[] words)
    {
        return Can(s, words, 0, new bool?[s.Length + 1]);
    }

    static bool Can(string s, string[] words, int start, bool?[] memo)
    {
        if (start == s.Length) return true;
        if (memo[start] is bool known) return known;
        bool result = false;
        foreach (string w in words)
        {
            if (s.AsSpan(start).StartsWith(w) && Can(s, words, start + w.Length, memo))
            {
                result = true;
                break;
            }
        }
        memo[start] = result;
        return result;
    }
}

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

ok[i] is true when the first i characters split into words; a new bool[] is all false, so only ok[0] needs setting. For each end, look back at most longest characters for a start with ok[start] set and the substring in the HashSet<string>.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool WordBreak(string s, string[] words)
    {
        var vocab = new HashSet<string>(words);
        int longest = words.Max(w => w.Length);
        var ok = new bool[s.Length + 1];
        ok[0] = true; // the empty prefix needs no words
        for (int end = 1; end <= s.Length; end++)
        {
            for (int start = Math.Max(0, end - longest); start < end; start++)
            {
                if (ok[start] && vocab.Contains(s.Substring(start, end - start)))
                {
                    ok[end] = true;
                    break;
                }
            }
        }
        return ok[s.Length];
    }
}

2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

can(start) answers whether s from start onward splits into words. s.compare(start, w.size(), w) == 0 checks a word in place without building a substring, and returns non-zero when fewer than w.size() characters remain. The memo member holds -1 for unknown, so each start is solved once.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
    vector<int> memo; // -1 = unknown, 0 = no, 1 = yes

    bool can(const string& s, const vector<string>& words, int start) {
        if (start == (int)s.size()) return true;
        if (memo[start] != -1) return memo[start] == 1;
        for (const string& w : words) {
            if (s.compare(start, w.size(), w) == 0 && can(s, words, start + (int)w.size())) {
                memo[start] = 1;
                return true;
            }
        }
        memo[start] = 0;
        return false;
    }

public:
    bool wordBreak(string s, vector<string>& words) {
        memo.assign(s.size() + 1, -1);
        return can(s, words, 0);
    }
};

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

ok[i] is true when the first i characters split into words. For each end, look back at most longest characters for a start with ok[start] set and s.substr(start, end - start) in the unordered_set. No recursion, and one hash lookup per check.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& words) {
        unordered_set<string> vocab(words.begin(), words.end());
        int longest = 0;
        for (const string& w : words) longest = max(longest, (int)w.size());
        int n = s.size();
        vector<bool> ok(n + 1, false);
        ok[0] = true; // the empty prefix needs no words
        for (int end = 1; end <= n; end++) {
            for (int start = max(0, end - longest); start < end; start++) {
                if (ok[start] && vocab.count(s.substr(start, end - start))) {
                    ok[end] = true;
                    break;
                }
            }
        }
        return ok[n];
    }
};

2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

can(start) answers whether s + start splits into words. Each word is checked in place with strncmp(s + start, words[i], lens[i]), which stops at the end of s, so a word longer than what is left never matches. The memo array holds 0 for unknown, 1 for yes and -1 for no, so every start is solved once.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static bool can(const char* s, int n, int start, char** words, const int* lens, int wordsSize,
                signed char* memo) {
    if (start == n) return true;
    if (memo[start] != 0) return memo[start] == 1;
    for (int i = 0; i < wordsSize; i++) {
        if (strncmp(s + start, words[i], lens[i]) == 0 &&
            can(s, n, start + lens[i], words, lens, wordsSize, memo)) {
            memo[start] = 1;
            return true;
        }
    }
    memo[start] = -1;
    return false;
}

bool wordBreak(char* s, char** words, int wordsSize) {
    int n = strlen(s);
    int* lens = malloc(wordsSize * sizeof *lens);
    for (int i = 0; i < wordsSize; i++) lens[i] = strlen(words[i]);
    signed char* memo = calloc(n + 1, sizeof *memo); // 0 = unknown, 1 = yes, -1 = no
    bool result = can(s, n, 0, words, lens, wordsSize, memo);
    free(memo);
    free(lens);
    return result;
}

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

ok[i] is true when the first i characters split into words. C has no built-in set, so a sorted copy of the dictionary plays that part: bsearch finds a piece of s by pointer and length, without copying it into a NUL-terminated buffer. For each end, only the last longest starts are tried.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    const char* text; // points into s, not NUL-terminated
    size_t len;
} Piece;

static int compare_words(const void* a, const void* b) {
    return strcmp(*(char* const*)a, *(char* const*)b);
}

static int compare_piece(const void* key, const void* elem) {
    const Piece* piece = key;
    const char* word = *(char* const*)elem;
    int c = strncmp(piece->text, word, piece->len);
    if (c != 0) return c;
    return word[piece->len] == 0 ? 0 : -1; // the word is longer, so the piece sorts first
}

bool wordBreak(char* s, char** words, int wordsSize) {
    int n = strlen(s);
    char** sorted = malloc(wordsSize * sizeof *sorted);
    memcpy(sorted, words, wordsSize * sizeof *sorted); // leave the caller's array in its order
    qsort(sorted, wordsSize, sizeof *sorted, compare_words);
    int longest = 0;
    for (int i = 0; i < wordsSize; i++) {
        int len = strlen(words[i]);
        if (len > longest) longest = len;
    }
    bool* ok = calloc(n + 1, sizeof *ok);
    ok[0] = true; // the empty prefix needs no words
    for (int end = 1; end <= n; end++) {
        for (int start = end > longest ? end - longest : 0; start < end; start++) {
            Piece piece = { s + start, (size_t)(end - start) };
            if (ok[start] && bsearch(&piece, sorted, wordsSize, sizeof *sorted, compare_piece)) {
                ok[end] = true;
                break;
            }
        }
    }
    bool result = ok[n];
    free(ok);
    free(sorted);
    return result;
}

2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

can(start) answers whether the bytes from start onward split into words. s[start..].starts_with(w.as_bytes()) checks a word in place, and iter().any stops at the first word that leads to a full split. The memo is a Vec<Option<bool>>, with None meaning not solved yet.

impl Solution {
    pub fn word_break(s: String, words: Vec<String>) -> bool {
        let mut memo = vec![None; s.len() + 1];
        Self::can(s.as_bytes(), &words, 0, &mut memo)
    }

    fn can(s: &[u8], words: &[String], start: usize, memo: &mut Vec<Option<bool>>) -> bool {
        if start == s.len() {
            return true;
        }
        if let Some(known) = memo[start] {
            return known;
        }
        let result = words.iter().any(|w| {
            s[start..].starts_with(w.as_bytes()) && Self::can(s, words, start + w.len(), memo)
        });
        memo[start] = Some(result);
        result
    }
}

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

ok[i] is true when the first i bytes split into words. The HashSet<&str> borrows the words, and &s[start..end] is a slice of s, so a lookup hashes the piece without allocating. For each end, only the last longest starts are tried.

use std::collections::HashSet;

impl Solution {
    pub fn word_break(s: String, words: Vec<String>) -> bool {
        let vocab: HashSet<&str> = words.iter().map(String::as_str).collect();
        let longest = words.iter().map(String::len).max().unwrap_or(0);
        let n = s.len();
        let mut ok = vec![false; n + 1];
        ok[0] = true; // the empty prefix needs no words
        for end in 1..=n {
            ok[end] = (end.saturating_sub(longest)..end).any(|start| ok[start] && vocab.contains(&s[start..end]));
        }
        ok[n]
    }
}

2 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

Swift strings cannot be indexed by an Int, so s and every word become [UInt8] arrays of their UTF-8 bytes first. can(start) answers whether the bytes from start onward split into words, checking each word in place with starts(with:) on a slice. The memo array of Bool? keeps one answer per start.

class Solution {
    func wordBreak(_ s: String, _ words: [String]) -> Bool {
        let chars = Array(s.utf8)
        let dict = words.map { Array($0.utf8) }
        var memo = [Bool?](repeating: nil, count: chars.count + 1)

        func can(_ start: Int) -> Bool {
            if start == chars.count { return true }
            if let known = memo[start] { return known }
            var result = false
            for w in dict where chars[start...].starts(with: w) {
                if can(start + w.count) {
                    result = true
                    break
                }
            }
            memo[start] = result
            return result
        }

        return can(0)
    }
}

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

ok[i] is true when the first i characters split into words. For each end, look back at most longest bytes for a start with ok[start] set and the piece in the Set; the piece is rebuilt with String(decoding:as:) from the byte slice. No recursion, and one hash lookup per check.

class Solution {
    func wordBreak(_ s: String, _ words: [String]) -> Bool {
        let vocab = Set(words)
        let longest = words.map { $0.utf8.count }.max() ?? 0
        let chars = Array(s.utf8)
        let n = chars.count
        var ok = [Bool](repeating: false, count: n + 1)
        ok[0] = true // the empty prefix needs no words
        if n == 0 { return true }
        for end in 1...n {
            for start in max(0, end - longest)..<end
            where ok[start] && vocab.contains(String(decoding: chars[start..<end], as: UTF8.self)) {
                ok[end] = true
                break
            }
        }
        return ok[n]
    }
}

2 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: try every word at each start, cache each start

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

can($start) answers whether $s from $start onward splits into words. substr_compare($s, $w, $start, strlen($w)) checks a word in place, without cutting a substring for each of the 1,000 words. The $memo property keeps one answer per start, so each start is solved once.

<?php

class Solution {
    private string $s;
    private array $words;
    private array $memo;

    /**
     * @param string $s
     * @param string[] $words
     * @return bool
     */
    function wordBreak(string $s, array $words): bool {
        $this->s = $s;
        $this->words = $words;
        $this->memo = [];
        return $this->can(0);
    }

    private function can(int $start): bool {
        if ($start === strlen($this->s)) {
            return true;
        }
        if (isset($this->memo[$start])) {
            return $this->memo[$start];
        }
        foreach ($this->words as $w) {
            $len = strlen($w);
            if (substr_compare($this->s, $w, $start, $len) === 0 && $this->can($start + $len)) {
                return $this->memo[$start] = true;
            }
        }
        return $this->memo[$start] = false;
    }
}

2 · Bottom-up: a table of breakable prefixes with a word set

O(n·k²) time · O(n + m·k) space

recommended

$ok[$i] is true when the first $i characters split into words. array_flip turns the word list into keys, so isset($vocab[$piece]) is a hash lookup. For each $end, only the last $longest starts are tried.

<?php

class Solution {
    /**
     * @param string $s
     * @param string[] $words
     * @return bool
     */
    function wordBreak(string $s, array $words): bool {
        $vocab = array_flip($words);
        $longest = max(array_map('strlen', $words));
        $n = strlen($s);
        $ok = array_fill(0, $n + 1, false);
        $ok[0] = true; // the empty prefix needs no words
        for ($end = 1; $end <= $n; $end++) {
            for ($start = max(0, $end - $longest); $start < $end; $start++) {
                if ($ok[$start] && isset($vocab[substr($s, $start, $end - $start)])) {
                    $ok[$end] = true;
                    break;
                }
            }
        }
        return $ok[$n];
    }
}

FAQ for C

Why strncmp instead of copying the piece and calling strcmp?

strncmp(s + start, word, len) compares in place and stops at the first difference, so most words are rejected after one character and nothing is allocated. It also stops at the NUL that ends s: if fewer than len characters remain, that NUL differs from the word's character and the result is non-zero, so no separate length check is needed.

Why store the word lengths before recursing?

strlen walks the whole word every time it is called. The memo version checks up to 1,000 words at each of 300 starts, so measuring every word once into lens saves that walk on each of those checks. The lengths are also what tells the recursion where the next piece starts.

How does bsearch find a piece that is not NUL-terminated?

The key is a Piece with a pointer into s and a length, and compare_piece compares the first len characters with strncmp. When they match, the piece equals the word only if the word ends right there (word[len] == 0); otherwise the word is longer and sorts after the piece. The array must be sorted with the same order, which strcmp in qsort gives.

Why copy the words before qsort?

The caller owns words, and sorting it in place would change the order the caller sees after the call. Copying the pointers costs one malloc of wordsSize pointers; the strings themselves are shared, not duplicated.

Could a hash table replace the sorted array?

Yes: hash every word into an open-addressing table, then hash each piece by pointer and length and compare with strncmp plus a length check. It turns each lookup from O(k log m) into O(k) on average, but for 1,000 words binary search takes about 10 comparisons and most of them fail on the first character.

Keep going

Course Schedule35 / 40 · Graphs · Medium

Try Word Break in Python (Word Break in Python), JavaScript (Word Break in JavaScript), TypeScript (Word Break in TypeScript), Java (Word Break in Java), Go (Word Break in Go), C# (Word Break in C#), C++ (Word Break in C++), Kotlin (Word Break in Kotlin), Rust (Word Break in Rust), Swift (Word Break in Swift), PHP (Word Break in PHP), Ruby (Word Break in Ruby), Dart (Word Break in Dart) or Scala (Word Break in Scala) instead.

word_break.c

C 15.3

Not run yet

+ 7 hidden

Input

s = "paintpaintbrush"
words = ["brush", "paint", "pain", "rush"]

Expected

true

paint + paint + brush covers the whole string, using paint twice.