MediumDynamic programming

Word Break

Q: Why type the memo as (boolean | undefined)[]?

An unsolved slot and a slot that holds false are different states. With boolean[] the type claims every slot is a boolean, and if (memo[start]) would look natural yet recompute every failed start. The wider type pushes you to compare with undefined.

Q: Why a Set instead of words.includes?

includes scans the whole array on every call, so with 1,000 words each check costs 1,000 comparisons. Set.has hashes the slice once and answers in constant time on average.

Q: Does the arrow function inside wordBreak cost anything?

It is created once per call to wordBreak and closes over s, words and memo, which saves passing them on every recursive call. The recursion depth is at most one frame per character, 300 here, far below the engine's stack limit.

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 TypeScript

Why type the memo as (boolean | undefined)[]?

An unsolved slot and a slot that holds false are different states. With boolean[] the type claims every slot is a boolean, and if (memo[start]) would look natural yet recompute every failed start. The wider type pushes you to compare with undefined.

Map<number, boolean> or an array for the memo?

Both work. The start positions are dense integers from 0 to s.length, so an array is the simpler and faster choice; a Map is handy when the keys are sparse or are not numbers.

Why a Set<string> instead of words.includes?

includes scans the whole array on every call, so with 1,000 words each check costs 1,000 comparisons. Set.has hashes the slice once and answers in constant time on average.

Does the arrow function inside wordBreak cost anything?

It is created once per call to wordBreak and closes over s, words and memo, which saves passing them on every recursive call. The recursion depth is at most one frame per character, 300 here, far below the engine's stack limit.

Does TypeScript make the solution faster?

No. The types are checked and then erased, so the code runs exactly like the JavaScript version. They catch mistakes such as returning ok instead of ok[s.length] before the code runs.

Keep going

Course Schedule35 / 40 · Graphs · Medium

Try Word Break in Python (Word Break in Python), JavaScript (Word Break in JavaScript), Java (Word Break in Java), Go (Word Break in Go), C# (Word Break in C#), 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.ts

TypeScript 5.9

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.