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

Kayar Pencere

Rehber 5 / 6 · Yol 5 / 6

← ÖncekiSonraki →

Etkileşimli

Zihinsel model

Bu problem için animasyonlu çözüm. Adımları kaydır veya boşlukla duraklat; değişmezi yüksek sesle yeniden anlat.

Adım 1 / 6
e
i
d
b
a
o
o
o
eşlema→1b→1

need = ab

s2, s1="ab" permütasyonu içeriyor mu? Aynı sayıma sahip uzunluk 2 pencere gerekir.

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

Mediumsliding-window

Permutation in String

Problem (yeniden ifade)

s2 içinde s1’in bir permütasyonunu bitişik alt dizgi olarak içeriyorsa true döndür.

Sezgi

s1’in permütasyonu, |s1| uzunluğunda ve aynı karakter sayımlarına sahip herhangi bir penceredir.

Yaklaşımlar

Sabit pencere frekans eşleşmesi

Doğrulanmadı
Zaman O(n)Alan O(1)

Fikir. s1 frekanslarını say. s2 üzerinde o uzunlukta bir pencere kaydır, sayımları karşılaştır (veya bir matches sayacı tut).

Yürüyüş. s1=“ab”, s2=“eidbaooo”. “ba” penceresi a,b sayımlarıyla eşleşir → true.

Trade-off. Küçük harf İngilizce için O(1) alfabet uzayı. Her pencereyi sıralamak daha yavaş.

Çözüm
export function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const need = new Array<number>(26).fill(0);
  const win = new Array<number>(26).fill(0);
  for (let i = 0; i < s1.length; i++) {
    need[s1.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i)! - 97]!++;
  }
  const eq = () => need.every((v, i) => v === win[i]);
  if (eq()) return true;
  for (let i = s1.length; i < s2.length; i++) {
    win[s2.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i - s1.length)! - 97]!--;
    if (eq()) return true;
  }
  return false;
}

export function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const need = new Array<number>(26).fill(0);
  const win = new Array<number>(26).fill(0);
  for (let i = 0; i < s1.length; i++) {
    need[s1.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i)! - 97]!++;
  }
  const eq = () => need.every((v, i) => v === win[i]);
  if (eq()) return true;
  for (let i = s1.length; i < s2.length; i++) {
    win[s2.charCodeAt(i)! - 97]!++;
    win[s2.charCodeAt(i - s1.length)! - 97]!--;
    if (eq()) return true;
  }
  return false;
}

Şablon bağlantısı

s1 sayımlarıyla eşleşen sabit uzunluklu sliding window (anagram / permütasyon).

Yansıma