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

Hardgrid-graph-bfs

Word Ladder

Problem (yeniden ifade)

beginWord, endWord ve bir kelime listesi verildiğinde, begin’den end’e en kısa dönüşüm dizisinin uzunluğunu döndür; her seferinde bir harf değişir, her ara kelime listede olmalıdır. İmkansızsa 0 döndür.

Sezgi

Örtük graf: kelimeler düğüm; Hamming mesafesi 1 ise kenar. begin’den BFS en kısa dizi uzunluğunu bulur (kelime sayısı).

Yaklaşımlar

Kelime grafında BFS

Tested only

Time O(N * L * 26)Space O(N)

Fikir. (kelime, dist) kuyruğu. Her konum için a-z komşularını dene; sette olanları al; ziyarette kaldır.

Adım adım. hit → hot → dot → dog → cog uzunluk 5.

Trade-off’lar. BFS ağırlıksız için optimal; çift yönlü BFS pratikte daha hızlı.

Solution

export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const q: [string, number][] = [[beginWord, 1]];
  const seen = new Set<string>([beginWord]);
  while (q.length) {
    const [w, d] = q.shift()!;
    if (w === endWord) return d;
    const arr = w.split("");
    for (let i = 0; i < arr.length; i++) {
      const orig = arr[i]!;
      for (let c = 97; c <= 122; c++) {
        arr[i] = String.fromCharCode(c);
        const next = arr.join("");
        if (set.has(next) && !seen.has(next)) {
          seen.add(next);
          q.push([next, d + 1]);
        }
      }
      arr[i] = orig;
    }
  }
  return 0;
}

export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const q: [string, number][] = [[beginWord, 1]];
  const seen = new Set<string>([beginWord]);
  while (q.length) {
    const [w, d] = q.shift()!;
    if (w === endWord) return d;
    const arr = w.split("");
    for (let i = 0; i < arr.length; i++) {
      const orig = arr[i]!;
      for (let c = 97; c <= 122; c++) {
        arr[i] = String.fromCharCode(c);
        const next = arr.join("");
        if (set.has(next) && !seen.has(next)) {
          seen.add(next);
          q.push([next, d + 1]);
        }
      }
      arr[i] = orig;
    }
  }
  return 0;
}

Şablon bağlantısı

Örtük komşulukta graf BFS.

Derinlemesine

Grafı örtük kur: bir kelimeden tüm tek harf mutasyonlarını dene ve kelime setinde kalanları tut. beginWord’den BFS, endWord’e ilk ulaştığında en kısa merdiveni garanti eder. Yoldaki kelimeleri say (begin 1 sayılır). Aynı kelime iki kez genişlemesin diye kuyruğa alırken ziyaret et. Çift yönlü BFS (her iki uçtan arama) büyük sözlüklerde yaygın bir sabit faktör hızlandırmadır.

Çift yönlü BFS

Tested only

Time O(N·L·26)Space O(N)

Fikir. begin ve end’den iki sınır büyüt; her adımda daha küçük tarafı genişlet. Buluşma en kısa merdiven demektir.

Trade-off’lar. En kötü durum tek yönlü BFS ile aynı sınıf; geniş sözlüklerde genelde daha az genişleme.

Solution

/** Bidirectional BFS on the word graph, meet in the middle. */
export function ladderLengthBi(beginWord: string, endWord: string, wordList: string[]): number {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  let front = new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  const seen = new Set<string>([beginWord, endWord]);
  let dist = 1;
  const neighbors = (w: string): string[] => {
    const out: string[] = [];
    const a = w.split("");
    for (let i = 0; i < a.length; i++) {
      const o = a[i]!;
      for (let c = 97; c <= 122; c++) {
        a[i] = String.fromCharCode(c);
        const n = a.join("");
        if (dict.has(n)) out.push(n);
      }
      a[i] = o;
    }
    return out;
  };
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set<string>();
    for (const w of front) {
      for (const n of neighbors(w)) {
        if (back.has(n)) return dist + 1;
        if (!seen.has(n)) {
          seen.add(n);
          next.add(n);
        }
      }
    }
    front = next;
    dist++;
  }
  return 0;
}

/** Bidirectional BFS on the word graph, meet in the middle. */
export function ladderLengthBi(beginWord: string, endWord: string, wordList: string[]): number {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  let front = new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  const seen = new Set<string>([beginWord, endWord]);
  let dist = 1;
  const neighbors = (w: string): string[] => {
    const out: string[] = [];
    const a = w.split("");
    for (let i = 0; i < a.length; i++) {
      const o = a[i]!;
      for (let c = 97; c <= 122; c++) {
        a[i] = String.fromCharCode(c);
        const n = a.join("");
        if (dict.has(n)) out.push(n);
      }
      a[i] = o;
    }
    return out;
  };
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set<string>();
    for (const w of front) {
      for (const n of neighbors(w)) {
        if (back.has(n)) return dist + 1;
        if (!seen.has(n)) {
          seen.add(n);
          next.add(n);
        }
      }
    }
    front = next;
    dist++;
  }
  return 0;
}

Yansıma

90 saniye içinde hangi kalıp bunu verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?