MediumDynamic programming

Word Break

Q: Why convert the string to Array(s.utf8)?

A Swift String is indexed by String.Index, not Int, and moving an index forward walks the characters, so s[s.index(s.startIndex, offsetBy: i)] is O(i). An array of bytes indexes in O(1). The input is lowercase ASCII, so one byte is one character and the positions line up.

Q: Why not use s.hasPrefix on a Substring?

hasPrefix lives in the standard library, but getting a Substring that starts at start still needs a String.Index built by walking start characters, and it compares by Unicode grapheme rules. chars[start...].starts(with: w) compares bytes directly and stops at the first difference, which is what the memo version wants with 1,000 words at each start.

Q: Can a nested function modify the memo array?

Yes. A nested func captures memo by reference, so writes inside can are visible to the next call. It also captures chars and dict, so the recursion only passes the start index.

Q: Why the n == 0 check before the loop?

A closed range 1...n traps at runtime when n is 0, because its lower bound would be above its upper bound. Returning early for the empty string, whose answer is true, avoids that; stride(from: 1, through: n, by: 1) is the other way, since it is simply empty.

Q: Do I need import Foundation for this?

No. Set, Array, String(decoding:as:) and starts(with:) are all in the standard library. Importing Foundation adds about 1.5 s to every Run on this site and nothing these solutions need.

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 Swift

Why convert the string to Array(s.utf8)?

A Swift String is indexed by String.Index, not Int, and moving an index forward walks the characters, so s[s.index(s.startIndex, offsetBy: i)] is O(i). An array of bytes indexes in O(1). The input is lowercase ASCII, so one byte is one character and the positions line up.

Why not use s.hasPrefix on a Substring?

hasPrefix lives in the standard library, but getting a Substring that starts at start still needs a String.Index built by walking start characters, and it compares by Unicode grapheme rules. chars[start...].starts(with: w) compares bytes directly and stops at the first difference, which is what the memo version wants with 1,000 words at each start.

Can a nested function modify the memo array?

Yes. A nested func captures memo by reference, so writes inside can are visible to the next call. It also captures chars and dict, so the recursion only passes the start index.

Why the n == 0 check before the loop?

A closed range 1...n traps at runtime when n is 0, because its lower bound would be above its upper bound. Returning early for the empty string, whose answer is true, avoids that; stride(from: 1, through: n, by: 1) is the other way, since it is simply empty.

Do I need import Foundation for this?

No. Set, Array, String(decoding:as:) and starts(with:) are all in the standard library. Importing Foundation adds about 1.5 s to every Run on this site and nothing these solutions need.

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), PHP (Word Break in PHP), Ruby (Word Break in Ruby), Dart (Word Break in Dart) or Scala (Word Break in Scala) instead.

word_break.swift

Swift 6.2

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.