Why arrayOfNulls instead of BooleanArray for the memo?

The memo needs three states: not solved, true and false. BooleanArray only has two and starts all false, so a nullable Array uses null for not solved. An IntArray with -1, 0 and 1 avoids boxing if it ever matters.

MediumDynamic programming

Word Break

Q: Does s.startsWith(w, start) create a substring?

No. Kotlin's startsWith(prefix, startIndex) maps to Java's String.startsWith(prefix, toffset), which compares characters in place and returns false when the word would run past the end. That matters here, because the memo version checks every word at every start.

Q: Can I return from inside words.any { }?

any is an inline function, so a bare return inside its lambda would return from can itself, and return@any would only end that one call of the lambda. Neither is needed: the lambda's last expression is its result, and any stops at the first true.

Q: Why a local function for the recursion?

A local fun can sees s, words and memo from the enclosing call, so the recursive call only passes the start index. The memo array is created per wordBreak call, so nothing carries over between strings. A private member function that takes the memo as a parameter works the same way.

Q: Is maxOf safe on the words array?

words.maxOf { it.length } throws NoSuchElementException on an empty array. The dictionary always has at least one word here; for input that could be empty, words.maxOfOrNull { it.length } ?: 0 returns 0 instead.

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 Kotlin

Does s.startsWith(w, start) create a substring?

No. Kotlin's startsWith(prefix, startIndex) maps to Java's String.startsWith(prefix, toffset), which compares characters in place and returns false when the word would run past the end. That matters here, because the memo version checks every word at every start.

Can I return from inside words.any { }?

any is an inline function, so a bare return inside its lambda would return from can itself, and return@any would only end that one call of the lambda. Neither is needed: the lambda's last expression is its result, and any stops at the first true.

Why a local function for the recursion?

A local fun can sees s, words and memo from the enclosing call, so the recursive call only passes the start index. The memo array is created per wordBreak call, so nothing carries over between strings. A private member function that takes the memo as a parameter works the same way.

Why arrayOfNulls<Boolean> instead of BooleanArray for the memo?

The memo needs three states: not solved, true and false. BooleanArray only has two and starts all false, so a nullable Array<Boolean?> uses null for not solved. An IntArray with -1, 0 and 1 avoids boxing if it ever matters.

Is maxOf safe on the words array?

words.maxOf { it.length } throws NoSuchElementException on an empty array. The dictionary always has at least one word here; for input that could be empty, words.maxOfOrNull { it.length } ?: 0 returns 0 instead.

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), 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.kt

Kotlin 2.4

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.