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

Mediumbacktracking

Palindrome Partitioning

Problem (yeniden ifade)

s dizesini her alt dize palindrom olacak şekilde böl. Tüm bu bölümlemeleri döndür.

Sezgi

Her başlangıç indeksinde, s[start..end] palindrom yapan her end’i dene, sonra özyinele.

Yaklaşımlar

Yalnızca palindrom öneklerde kes

Tested only

Time O(n * 2^n)Space O(n)

Fikir. dfs(start): start==n ise yolu kaydet; end≥start için palindromsa dilimi al, dfs(end+1), geri al.

Adım adım. “aab” → [[“a”,“a”,“b”],[“aa”,“b”]].

Trade-off’lar. O(1) kontroller için isPal[i][j] önceden hesaplanabilir; mülakat n’i için basit iki işaretçi kontrolü yeterli.

Solution

export function partition(s: string): string[][] {
  const res: string[][] = [];
  const path: string[] = [];
  const isPal = (l: number, r: number): boolean => {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  };
  const dfs = (start: number) => {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start, end)) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

export function partition(s: string): string[][] {
  const res: string[][] = [];
  const path: string[] = [];
  const isPal = (l: number, r: number): boolean => {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  };
  const dfs = (start: number) => {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start, end)) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

Şablon bağlantısı

Kesim konumları üzerinde geçerlilik filtresiyle backtracking.

Yansıma

90 saniye içinde hangi kalıp bunu verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?