139. Word Break

Return true if s can be split into a sequence of one or more words from wordDict. Words may be reused.

Treat each index as a node with an edge i → i + len(w) when word w matches at i. Is index n reachable from 0?

1function wordBreak(s: string, wordDict: string[]): boolean {
2  const queue = [0], seen = new Set([0]);
3  while (queue.length) {
4    const i = queue.shift()!;
5    for (const w of wordDict) {
6      if (!s.startsWith(w, i)) continue;
7      const next = i + w.length;
8      if (next === s.length) return true;
9      if (!seen.has(next)) { seen.add(next); queue.push(next); }
10    }
11  }
12  return false;
13}

s

queue

Start from index 0.

1 / 0

Space: play/pause · ←/→: step