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

Shortest Palindrome

Problem (yeniden ifade)

s’ye en kısa öneki ekle ki sonuç palindrom olsun. Yalnızca öne ekleyebilirsin.

Sezgi

Zaten palindrom olan en uzun öneki iste, kalan sonekin tersini öne koy. O önek s + '#' + reverse(s)’nin lps[-1]’idir: # sarmayı keser.

Yaklaşımlar

s + # + reverse(s) LPS

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. comb = s + '#' + reverse(s). LPS kur. reverse(s)[0 : n - lps[-1]]’i s’nin önüne ekle.

Yürüyüş. aacecaaa → palindrom önek aacecaa, kalan a, öne a → aaacecaaa.

Trade-off. # şart; yoksa LPS birleşimden atlar. Naif merkezden genişleme O(n²).

Çözüm

function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  return lps;
}

export function shortestPalindrome(s: string): string {
  if (!s) return s;
  const rev = [...s].reverse().join("");
  const lps = buildLps(`${s}#${rev}`);
  return rev.slice(0, s.length - lps[lps.length - 1]!) + s;
}

function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  return lps;
}

export function shortestPalindrome(s: string): string {
  if (!s) return s;
  const rev = [...s].reverse().join("");
  const lps = buildLps(`${s}#${rev}`);
  return rev.slice(0, s.length - lps[lps.length - 1]!) + s;
}

Şablon bağlantısı

Pattern + reverse LPS ile shortest palindrome. LC 28 ile aynı LPS kurucu.

Yansıma

s + '#' + ters(s) dizisinin LPS’si, s’in en uzun palindromik öneki. Başa eklenecek parça tersin kalanı.
# önek ile sonekin birbirine taşmasını keser. S zaten palindromsa ekleme boş.
Tek karakter kendisi. Ayraç olmazsa LPS yanlış uzar.