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

Mediumhashing

Group Anagrams

Problem (yeniden ifade)

Bir string dizisi verildiğinde anagramları grupla. Grup sırası ve grup içi sıra herhangi bir şey olabilir.

Sezgi

Anagramlar bir imza paylaşır: sıralı karakterler veya 26’lık sayım demeti. Hash map imza → kelime listesi.

Yaklaşımlar

Sıralı anahtarlı hash map

Doğrulanmadı

Zaman O(n · k log k)Alan O(n · k)

Fikir. Her kelime için key = sorted(word). Kelimeyi map[key]’e ekle.

Yürüyüş. [“eat”,“tea”,“tan”,“ate”] → “aet” anahtarı eat/tea/ate grubu; “ant” tan grubu.

Trade-off. Basit. Sayım dizisi anahtarı O(n·k) ve k büyükken daha hızlı.

Çözüm

export function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = [...s].sort().join("");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

export function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = [...s].sort().join("");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

Sayım imzalı hash map

Doğrulanmadı

Zaman O(n · k)Alan O(n · k)

Fikir. 26 harf sayımından string (veya tuple) olarak birleştirilmiş anahtar.

Yürüyüş. Aynı gruplama, toplam karakterde doğrusal.

Trade-off. Uzun string’lerde daha iyi asemptotik; biraz daha fazla kod.

Çözüm

export function groupAnagramsCount(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const cnt = new Array(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    const key = cnt.join("#");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

export function groupAnagramsCount(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const cnt = new Array(26).fill(0);
    for (const ch of s) cnt[ch.charCodeAt(0) - 97]++;
    const key = cnt.join("#");
    const bucket = map.get(key) ?? [];
    bucket.push(s);
    map.set(key, bucket);
  }
  return [...map.values()];
}

Şablon bağlantısı

Hashing şablonundaki groupByKey. anahtar anagram imzası.

Yansıma

Anagramları gruplamak için sıralı anahtar mı, 26’lık sayım mı? Hangisi k uzunluğunda daha ucuz?
Boş string ve tek harfli girdiler ayrı gruplar mı, aynı grup mu?
Anahtarı join etmezsen (listeyi map anahtarı yaparsan) hangi dilde kırılır?