İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarTekrarlarHakkında
Dil
EnglishTürkçe

İki Boyutlu DP

Rehber 4 / 6 · Yol 4 / 6

← ÖncekiSonraki →

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

Mediumtwo-dimensional-dp

Edit Distance

Problem (yeniden ifade)

word1’i word2’ye dönüştür: ekle, sil veya değiştir (her biri maliyet 1). Minimum işlem sayısını döndür.

Sezgi

dp[i][j] = önekler word1[:i] ve word2[:j] için min işlem. Eşleşme çaprazı kopyalar; aksi halde sil, ekle veya değiştir + 1’in en iyisi.

Yaklaşımlar

Klasik Levenshtein DP

Tested only
Time O(m·n)Space O(m·n)

Fikir. Tam tablo. Taban: dp[i][0]=i, dp[0][j]=j. Eşit karakterler → çapraz; değilse üç komşunun 1 + min’i.

Adım adım. "horse" → "ros" 3 işlem ister.

Ödünleşimler. En net yineleme; tam O(mn) bellek kullanır.

Solution
export function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i]![0] = i;
  for (let j = 0; j <= n; j++) dp[0]![j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i]![j] = dp[i - 1]![j - 1]!;
      } else {
        dp[i]![j] =
          1 + Math.min(dp[i - 1]![j - 1]!, dp[i - 1]![j]!, dp[i]![j - 1]!);
      }
    }
  }
  return dp[m]![n]!;
}

export function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i]![0] = i;
  for (let j = 0; j <= n; j++) dp[0]![j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i]![j] = dp[i - 1]![j - 1]!;
      } else {
        dp[i]![j] =
          1 + Math.min(dp[i - 1]![j - 1]!, dp[i - 1]![j]!, dp[i]![j - 1]!);
      }
    }
  }
  return dp[m]![n]!;
}

Kaydıran satır DP

Tested only
Time O(m·n)Space O(min(m,n))

Fikir. Yalnızca önceki satırı tut. İsteğe bağlı olarak kısa kelimeyi sütun eksenine koy.

Ödünleşimler. Aynı süre, doğrusal alan. Önce 2B tabloyu öğren, sonra sıkıştır.

Solution
/** Space-optimized edit distance: one rolling row O(min(m,n)). */
export function minDistanceRolling(word1: string, word2: string): number {
  if (word1.length < word2.length) [word1, word2] = [word2, word1];
  const m = word1.length, n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  for (let i = 1; i <= m; i++) {
    const cur = new Array<number>(n + 1);
    cur[0] = i;
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) cur[j] = prev[j - 1]!;
      else cur[j] = 1 + Math.min(prev[j]!, cur[j - 1]!, prev[j - 1]!);
    }
    prev = cur;
  }
  return prev[n]!;
}

/** Space-optimized edit distance: one rolling row O(min(m,n)). */
export function minDistanceRolling(word1: string, word2: string): number {
  if (word1.length < word2.length) [word1, word2] = [word2, word1];
  const m = word1.length, n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  for (let i = 1; i <= m; i++) {
    const cur = new Array<number>(n + 1);
    cur[0] = i;
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) cur[j] = prev[j - 1]!;
      else cur[j] = 1 + Math.min(prev[j]!, cur[j - 1]!, prev[j - 1]!);
    }
    prev = cur;
  }
  return prev[n]!;
}

Şablon bağlantısı

İki string hizalama DP’si (LCS ile aynı aile).

Derinlemesine

Yansıma