演算法

1// 1. Backtracking: try every first word, recurse on the rest. Exponential.
2function wordBreakBacktrack(s: string, words: string[]): boolean {
3  const dict = new Set(words);
4  const solve = (start: number): boolean => {
5    if (start === s.length) return true;
6    for (let end = start + 1; end <= s.length; end++) {
7      if (dict.has(s.slice(start, end)) && solve(end)) return true;
8    }
9    return false;
10  };
11  return solve(0);
12}
13 
14// 2. The same recursion, answering each start index only once. O(n²).
15function wordBreakMemo(s: string, words: string[]): boolean {
16  const dict = new Set(words);
17  const memo = new Map<number, boolean>();
18  const solve = (start: number): boolean => {
19    if (memo.has(start)) return memo.get(start)!;
20    if (start === s.length) return true;
21    for (let end = start + 1; end <= s.length; end++) {
22      if (dict.has(s.slice(start, end)) && solve(end)) {
23        memo.set(start, true);
24        return true;
25      }
26    }
27    memo.set(start, false);
28    return false;
29  };
30  return solve(0);
31}
32 
33// 3. Bottom-up: dp[i] says whether the first i characters split. O(n²).
34function wordBreakDp(s: string, words: string[]): boolean {
35  const dict = new Set(words);
36  const dp = new Array(s.length + 1).fill(false);
37  dp[0] = true;
38  for (let i = 1; i <= s.length; i++) {
39    for (let j = 0; j < i; j++) {
40      if (dp[j] && dict.has(s.slice(j, i))) {
41        dp[i] = true;
42        break;
43      }
44    }
45  }
46  return dp[s.length];
47}
48 
49// 4. BFS over indices: a word from i to j is an edge. O(n²).
50function wordBreakBfs(s: string, words: string[]): boolean {
51  const dict = new Set(words);
52  const seen = new Array(s.length + 1).fill(false);
53  const queue = [0];
54  seen[0] = true;
55  while (queue.length) {
56    const start = queue.shift()!;
57    for (let end = start + 1; end <= s.length; end++) {
58      if (!dict.has(s.slice(start, end)) || seen[end]) continue;
59      if (end === s.length) return true;
60      seen[end] = true;
61      queue.push(end);
62    }
63  }
64  return false;
65}