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

Mediumstack-parsing

Decode String

Problem (yeniden ifade)

3[a2[c]] gibi kodlanmış string → accaccacc. Rakamlar tekrar sayısı; köşeli parantezler iç içe.

Sezgi

İki yığın (veya çerçeve yığını): sayaçlar ve string builder’lar. ] gelince pop et ve tekrarla.

Yaklaşımlar

Yığın ile parse

Doğrulanmadı

Zaman O(n · output)Alan O(output)

Fikir. Rakamda k biriktir; [ gelince çerçeve push et; harfte ekle; ] gelince tekrarla ve birleştir.

Yürüyüş. 3[a]2[bc] → aaabcbc; 3[a2[c]] → accaccacc.

Trade-off. Özyinelemeli iniş de olur; yığın çağrı çerçevelerini yansıtır.

Çözüm

export function decodeString(s: string): string {
  const countSt: number[] = [];
  const strSt: string[] = [];
  let cur = "";
  let k = 0;
  for (const ch of s) {
    if (ch >= "0" && ch <= "9") k = k * 10 + (ch.charCodeAt(0) - 48);
    else if (ch === "[") {
      countSt.push(k);
      strSt.push(cur);
      cur = "";
      k = 0;
    } else if (ch === "]") {
      const times = countSt.pop()!;
      const prev = strSt.pop()!;
      cur = prev + cur.repeat(times);
    } else cur += ch;
  }
  return cur;
}

export function decodeString(s: string): string {
  const countSt: number[] = [];
  const strSt: string[] = [];
  let cur = "";
  let k = 0;
  for (const ch of s) {
    if (ch >= "0" && ch <= "9") k = k * 10 + (ch.charCodeAt(0) - 48);
    else if (ch === "[") {
      countSt.push(k);
      strSt.push(cur);
      cur = "";
      k = 0;
    } else if (ch === "]") {
      const times = countSt.pop()!;
      const prev = strSt.pop()!;
      cur = prev + cur.repeat(times);
    } else cur += ch;
  }
  return cur;
}

Şablon bağlantısı

İç içe yapıların yığın ile parse edilmesi.

Yansıma

Rakam çok basamaklı: 12[a]. [ görünce tekrar sayısını ve o ana kadarki dizgiyi it.
] iç dizgiyi k kez dışa yapıştırır. İç içe 3[a2[c]].
k = 0 boş üretir. k’sız harf düz metin. Yığın sonda boşalmış olmalı.