Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumone-dimensional-dp

Word Break

Problem (restated)

Can string s be segmented into a space-separated sequence of one or more dictionary words? Words may reuse.

Intuition

dp[i] = true if s[:i] can be segmented. Transition: some j < i with dp[j] and s[j:i] in dict.

Approaches

Prefix reachable DP

Tested only

Time O(n^2)Space O(n)

Idea. Hash set for O(1) word checks. dp[0]=true base.

Walkthrough. s=leetcode, dict=[leet,code] → true at n.

Trade-offs. Trie of dict prunes failed prefixes; BFS also works.

Solution

export function wordBreak(s: string, wordDict: string[]): boolean {
  const set = new Set(wordDict);
  const n = s.length;
  const dp = Array(n + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n]!;
}

export function wordBreak(s: string, wordDict: string[]): boolean {
  const set = new Set(wordDict);
  const n = s.length;
  const dp = Array(n + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n]!;
}

Template connection

1D DP on string prefixes / unbounded word reuse.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?