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

Alien Dictionary

Problem (yeniden ifade)

Sözcükler yabancı bir alfabeye göre sıralı. Geçerli bir harf sırası türet. Geçersiz önek durumu → "". Birden fazla geçerli topo sırası varsa herhangi biri kabul.

Sezgi

Ardışık sözcükleri karşılaştır; ilk farklı karakterler a→b öncelik kenarı verir (a, b’den önce). Sıra için Kahn BFS; döngü → "".

Yaklaşımlar

Sıralı çiftlerden Kahn sırası

Doğrulanmadı

Zaman O(C + E)Alan O(C + E)

Fikir. Benzersiz harflerden graf kur. Daha uzun sözcük, daha kısanın öneki iken önce listelenmişse reddet. Kalanı topo sırala.

Adım adım. [“wrt”,“wrf”,“er”,“ett”,“rftt”] → “wertf”.

Trade-off’lar. Birden fazla geçerli sıra vardır; testler doğru herhangi bir toplam sırayı veya sabit deterministik birini kabul eder.

Çözüm

export function alienOrder(words: string[]): string {
  const chars = new Set<string>();
  for (const w of words) for (const c of w) chars.add(c);
  const g = new Map<string, Set<string>>();
  const indeg = new Map<string, number>();
  for (const c of chars) {
    g.set(c, new Set());
    indeg.set(c, 0);
  }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i]!, b = words[i + 1]!;
    let j = 0;
    while (j < a.length && j < b.length && a[j] === b[j]) j++;
    if (j === b.length && a.length > b.length) return "";
    if (j < a.length && j < b.length && !g.get(a[j]!)!.has(b[j]!)) {
      g.get(a[j]!)!.add(b[j]!);
      indeg.set(b[j]!, indeg.get(b[j]!)! + 1);
    }
  }
  const q = [...chars].filter((c) => indeg.get(c) === 0).sort();
  const res: string[] = [];
  while (q.length) {
    const u = q.shift()!;
    res.push(u);
    for (const v of [...g.get(u)!].sort()) {
      indeg.set(v, indeg.get(v)! - 1);
      if (indeg.get(v) === 0) q.push(v);
    }
  }
  return res.length === chars.size ? res.join("") : "";
}

export function alienOrder(words: string[]): string {
  const chars = new Set<string>();
  for (const w of words) for (const c of w) chars.add(c);
  const g = new Map<string, Set<string>>();
  const indeg = new Map<string, number>();
  for (const c of chars) {
    g.set(c, new Set());
    indeg.set(c, 0);
  }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i]!, b = words[i + 1]!;
    let j = 0;
    while (j < a.length && j < b.length && a[j] === b[j]) j++;
    if (j === b.length && a.length > b.length) return "";
    if (j < a.length && j < b.length && !g.get(a[j]!)!.has(b[j]!)) {
      g.get(a[j]!)!.add(b[j]!);
      indeg.set(b[j]!, indeg.get(b[j]!)! + 1);
    }
  }
  const q = [...chars].filter((c) => indeg.get(c) === 0).sort();
  const res: string[] = [];
  while (q.length) {
    const u = q.shift()!;
    res.push(u);
    for (const v of [...g.get(u)!].sort()) {
      indeg.set(v, indeg.get(v)! - 1);
      if (indeg.get(v) === 0) q.push(v);
    }
  }
  return res.length === chars.size ? res.join("") : "";
}

Şablon bağlantısı

Öncelik kısıtlarından topolojik sıralama.

Yansıma

Ardışık kelimelerde ilk farklı harf bir kenar: soldaki harf önce gelir. abc sonra ab geçersizdir; kısa kelime uzun olanın öneki olup sonra gelemez.
Kahn harf sırası. Döngü boş dizgi. Çıktıda yalnızca görülen harfler.
Tek kelime kenar üretmez. Eşit iki kelime de kenar üretmez.