MediumDynamic programming

Word Break

Q: Why substr_compare instead of substr($s, $start, strlen($w)) === $w?

substr builds a new string for every check, and the memo version checks up to 1,000 words at each of 300 starts. substr_compare compares in place and returns a non-zero value when fewer than strlen($w) characters remain, so a word that runs past the end does not match. On PHP 8, str_starts_with(substr($s, $start), $w) reads well but copies the whole rest of the string each time.

Q: Why isset($this->memo[$start]) and not empty()?

empty() treats a stored false as missing, so every start that failed would be solved again and the cache would only remember successes. isset is true for any non-null value, so both answers count as known.

Q: Why array_flip instead of in_array?

in_array scans the whole list, so each check costs O(m) comparisons. array_flip makes each word a key, and isset($vocab[$piece]) is a hash lookup. The values (the old indices) are never used; only whether the key exists matters.

Q: Do numeric-looking words break array_flip?

PHP turns string keys like '12' into integer keys, but isset($vocab['12']) converts the lookup key the same way, so the check still works. The words here are lowercase letters only, so it never comes up.

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 PHP

Why substr_compare instead of substr($s, $start, strlen($w)) === $w?

substr builds a new string for every check, and the memo version checks up to 1,000 words at each of 300 starts. substr_compare compares in place and returns a non-zero value when fewer than strlen($w) characters remain, so a word that runs past the end does not match. On PHP 8, str_starts_with(substr($s, $start), $w) reads well but copies the whole rest of the string each time.

Why does the recursion keep $s and $memo as properties?

A method cannot see the caller's local variables, so the alternatives are passing them on every call (with &$memo by reference, or PHP copies the array on write) or storing them on the object. wordBreak resets the properties first, so a reused Solution never sees answers from a previous string.

Why isset($this->memo[$start]) and not empty()?

empty() treats a stored false as missing, so every start that failed would be solved again and the cache would only remember successes. isset is true for any non-null value, so both answers count as known.

Why array_flip instead of in_array?

in_array scans the whole list, so each check costs O(m) comparisons. array_flip makes each word a key, and isset($vocab[$piece]) is a hash lookup. The values (the old indices) are never used; only whether the key exists matters.

Do numeric-looking words break array_flip?

PHP turns string keys like '12' into integer keys, but isset($vocab['12']) converts the lookup key the same way, so the check still works. The words here are lowercase letters only, so it never comes up.

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++), C (Word Break in C), Kotlin (Word Break in Kotlin), Rust (Word Break in Rust), Swift (Word Break in Swift), Ruby (Word Break in Ruby), Dart (Word Break in Dart) or Scala (Word Break in Scala) instead.

word_break.php

PHP 8.5

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.