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 (yeniden ifade)

s dizgisi, bir veya daha fazla sözlük kelimesinin boşlukla ayrılmış dizisine bölünebilir mi? Kelimeler yeniden kullanılabilir.

Sezgi

dp[i] = true eğer s[:i] bölünebiliyorsa. Geçiş: dp[j] ve s[j:i] sözlükte olacak şekilde bir j < i.

Yaklaşımlar

Önek ulaşılabilir DP

Doğrulanmadı

Zaman O(n^2)Alan O(n)

Fikir. O(1) kelime kontrolü için hash set. dp[0]=true taban.

Yürüyüş. s=leetcode, dict=[leet,code] → n’de true.

Trade-off. Sözlüğün trie’ı başarısız önekleri budar; BFS de çalışır.

Çözüm

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]!;
}

Şablon bağlantısı

Dizgi öneklerinde 1D DP / sınırsız kelime yeniden kullanımı.

Yansıma

dp[i]: s[0:i] sözlükten bölünür mü. s[j:i] sözlükte ve dp[j] ise true.
dp[0] boş önek true. Sözlükte boş kelime olsaydı döngü kapanır; problemde yok.
Sona varılamazsa false. Tek harf sözlükteyse true.