Palindrome Partitioning: cắt chuỗi cho đến khi mỗi mảnh đọc xuôi ngược đều như nhau

Constraint là 1 <= s.length <= 16. Con số mười sáu đó là cả câu chuyện. Mười sáu ký tự nghĩa là tối đa mười lăm vị trí cắt, và tối đa 2^15 = 32768 tập con của các vị trí đó. Ngay cả approach brute-force kiểm tra palindrome inline qua từng partition cũng chạy nhanh. Constraint không ép bạn phải dùng backtracking — nó đang trao cho bạn quyền liệt kê tất cả mọi thứ. Bạn có precompute gì hay không chỉ là trade-off về hằng số, không phải vấn đề correctness.

Output là "tất cả các cách phân hoạch sao cho mỗi mảnh là palindrome." Hai ví dụ làm rõ cấu trúc: với "aab", kết quả là ["a","a","b"] và ["aa","b"]. Với "a", chỉ có ["a"] — một ký tự đơn lẻ luôn là palindrome.

Đề bài

Cho một chuỗi s, hãy phân hoạch s sao cho mọi substring trong phân hoạch đều là palindrome, và trả về tất cả các cách phân hoạch palindrome có thể. Full statement: LeetCode 131.

Ràng buộc:
- 1 <= s.length <= 16
- s chỉ chứa chữ cái thường tiếng Anh.

Constraints nói gì về không gian thiết kế

s.length <= 16 và chỉ có chữ thường tiếng Anh. Cả hai constraint đều có tác dụng thực sự.

n <= 16 loại bỏ mọi lo ngại về exponential blowup trong thực tế. Trong trường hợp xấu nhất, input toàn ký tự giống nhau ("aaaa...a"), khi đó mọi prefix đều là palindrome và recursion rẽ nhánh tại mỗi bước. Số partitions tối đa bằng số cách phân tổ hợp của n, tức là 2^(n-1). Với n = 16, đó là 32768. Nhanh.

Chỉ có chữ thường nghĩa là tối đa 26 ký tự phân biệt. Kiểm tra palindrome đơn giản (không cần chuẩn hoá hoa/thường) và khởi tạo DP trivial. Không bao giờ phải lo Unicode hay ký tự đặc biệt.

Không constraint nào nói "tìm số lần cắt tối thiểu" — đó là LeetCode 132, bài khó hơn. Ở đây bạn liệt kê, không tối ưu hoá.

Approach 1: Backtracking với kiểm tra palindrome inline

Recursion rất trực quan: bắt đầu tại vị trí start, thử mọi prefix kết thúc tại end, kiểm tra xem s[start:end] có phải palindrome không, nếu có thì thêm vào path hiện tại và recurse từ end. Khi start đạt đến độ dài chuỗi, ghi lại partition hoàn chỉnh.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        def is_palindrome(t: str) -> bool:
            return t == t[::-1]
 
        def backtrack(start: int, path: list[str]) -> None:
            if start == len(s):
                result.append(path[:])
                return
            for end in range(start + 1, len(s) + 1):
                sub = s[start:end]
                if is_palindrome(sub):
                    path.append(sub)
                    backtrack(end, path)
                    path.pop()
 
        result: list[list[str]] = []
        backtrack(0, [])
        return result

public class Solution {
    public IList<IList<string>> Partition(string s) {
        var result = new List<IList<string>>();
 
        bool IsPalindrome(string t) {
            int l = 0, r = t.Length - 1;
            while (l < r) {
                if (t[l] != t[r]) return false;
                l++; r--;
            }
            return true;
        }
 
        void Backtrack(int start, List<string> path) {
            if (start == s.Length) {
                result.Add(new List<string>(path));
                return;
            }
            for (int end = start + 1; end <= s.Length; end++) {
                string sub = s.Substring(start, end - start);
                if (IsPalindrome(sub)) {
                    path.Add(sub);
                    Backtrack(end, path);
                    path.RemoveAt(path.Count - 1);
                }
            }
        }
 
        Backtrack(0, new List<string>());
        return result;
    }
}

C# dùng two pointers cho IsPalindrome vì C# không có cú pháp reverse chuỗi ngắn gọn như [::-1] của Python. Cả hai đều O(k) với substring độ dài k.

Trace tay qua "aab"

Từng bước:

• start=0. Thử "a" (palindrome) -> path = ["a"], recurse với start=1.
  • start=1. Thử "a" (palindrome) -> path = ["a","a"], recurse với start=2.
    • start=2. Thử "b" (palindrome) -> path = ["a","a","b"], recurse với start=3.
      • start=3 == len(s) -> ghi lại ["a","a","b"].
    • Pop "b".
  • Pop "a". Thử "ab" -> không phải palindrome, bỏ qua.
  • Hết nhánh.
• Pop "a" đầu tiên. Thử "aa" (palindrome) -> path = ["aa"], recurse với start=2.
  • start=2. Thử "b" (palindrome) -> path = ["aa","b"], recurse với start=3.
    • start=3 == len(s) -> ghi lại ["aa","b"].
  • Pop "b".
• Pop "aa". Thử "aab" -> không phải palindrome, bỏ qua.
• Xong. Kết quả: [["a","a","b"], ["aa","b"]].

Complexity của Approach 1

Time: O(n * 2^n). Backtracking duyệt O(2^n) partitions trong trường hợp xấu nhất (input toàn ký tự giống nhau). Mỗi partition tốn O(n) để copy path tại leaf. Kiểm tra palindrome inline cũng cộng thêm O(n) mỗi candidate prefix qua từng level. Term chi phối là O(n * 2^n).

Space: O(n) auxiliary — độ sâu recursion tối đa là n (mỗi level tiêu thụ ít nhất một ký tự), và path giữ tối đa n phần tử. Danh sách result tự nó tăng đến O(2^n * n) trong trường hợp xấu nhất, nhưng đó là output space, không phải working space.

Approach 2: DP tiền xử lý, sau đó backtracking

Sự kém hiệu quả của Approach 1 nằm ở chỗ cùng một substring — ví dụ s[0:3] — có thể được kiểm tra palindrome nhiều lần qua các nhánh recursion khác nhau. Cách khắc phục là tính trước tất cả trạng thái palindrome trong một bảng boolean 2D, để mỗi lần gọi isPalindrome(s[i..j]) trong quá trình search chỉ là tra cứu O(1).

Recurrence DP là chuẩn: dp[i][j] là true nếu s[i] == s[j] và dp[i+1][j-1] là true. Base case: mọi ký tự đơn dp[i][i] = true; cặp dp[i][i+1] = (s[i] == s[i+1]). Điền theo độ dài tăng dần.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
 
        # Xây dựng bảng palindrome
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for i in range(n - 1):
            dp[i][i + 1] = s[i] == s[i + 1]
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
 
        def backtrack(start: int, path: list[str]) -> None:
            if start == n:
                result.append(path[:])
                return
            for end in range(start, n):
                if dp[start][end]:
                    path.append(s[start : end + 1])
                    backtrack(end + 1, path)
                    path.pop()
 
        result: list[list[str]] = []
        backtrack(0, [])
        return result

public class Solution {
    public IList<IList<string>> Partition(string s) {
        int n = s.Length;
        var result = new List<IList<string>>();
 
        // Xây dựng bảng palindrome
        bool[,] dp = new bool[n, n];
        for (int i = 0; i < n; i++) dp[i, i] = true;
        for (int i = 0; i < n - 1; i++) dp[i, i + 1] = s[i] == s[i + 1];
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i, j] = s[i] == s[j] && dp[i + 1, j - 1];
            }
        }
 
        void Backtrack(int start, List<string> path) {
            if (start == n) {
                result.Add(new List<string>(path));
                return;
            }
            for (int end = start; end < n; end++) {
                if (dp[start, end]) {
                    path.Add(s.Substring(start, end - start + 1));
                    Backtrack(end + 1, path);
                    path.RemoveAt(path.Count - 1);
                }
            }
        }
 
        Backtrack(0, new List<string>());
        return result;
    }
}

Lưu ý sự dịch chỉ mục: trong Approach 1, vòng lặp chạy for end in range(start + 1, len(s) + 1) và slice s[start:end]. Trong Approach 2, vòng lặp chạy for end in range(start, n) và index dp[start][end], rồi slice s[start:end+1]. Cả hai đều bao phủ cùng các substring; Approach 2 dùng chỉ mục end inclusive vì đó là biểu diễn tự nhiên cho bảng DP (dp[i][j] bao phủ s[i..j] inclusive).

Cách bảng DP điền cho "aab"

Chỉ mục:  0='a'  1='a'  2='b'

Độ dài 1 (base):
  dp[0][0] = True   ("a")
  dp[1][1] = True   ("a")
  dp[2][2] = True   ("b")

Độ dài 2:
  dp[0][1] = (s[0]==s[1]) = ('a'=='a') = True    ("aa")
  dp[1][2] = (s[1]==s[2]) = ('a'=='b') = False   ("ab")

Độ dài 3:
  dp[0][2] = (s[0]==s[2]) and dp[1][1]
           = ('a'=='b') and True
           = False                                  ("aab")

Bảng cuối (dp[i][j], hàng=i, cột=j):
       j=0    j=1    j=2
i=0    T      T      F
i=1           T      F
i=2                  T

Giờ backtracking đọc dp[0][0]=T (lấy "a"), dp[0][1]=T (lấy "aa"), dp[0][2]=F (bỏ "aab"). Tại start=1 đọc dp[1][1]=T (lấy "a"), dp[1][2]=F (bỏ "ab"). Recursion không bao giờ đánh giá lại palindrome — mỗi tra cứu chỉ là indexing mảng.

Complexity của Approach 2

Time: O(n^2 + n * 2^n). Việc điền DP là O(n^2) — có n^2 / 2 ô trong bảng và mỗi ô điền trong O(1). Backtracking vẫn là O(n * 2^n) trong trường hợp xấu nhất vì lý do tương tự. Với n = 16, n^2 = 256 hoàn toàn bị chi phối bởi term backtracking.

Space: O(n^2) cho bảng DP cộng O(n) cho call stack và path. Bảng là grid boolean n x n.

Các edge case quan trọng

Ký tự đơn (s = "a"): trong cả hai approach, start=0, ký tự đơn là palindrome, start đạt 1 bằng len(s), và ["a"] được ghi lại. Một kết quả, đúng.

Toàn ký tự giống nhau (s = "aaaa"): mọi substring đều là palindrome. Backtracking bùng nổ thành 2^(n-1) kết quả (tất cả các cách phân tổ hợp của n). Với n = 16, đó là 32768. Approach 1 đánh giá lại palindrome nhiều lần (mọi prefix của "aaaa..." được kiểm tra nhiều lần qua các nhánh khác nhau); Approach 2 kiểm tra mỗi dp[i][j] một lần. Sự khác biệt về hằng số rõ nhất ở đây.

Không có palindrome nào dài hơn 1 (s = "abcd"): mọi lần cắt trong output đều là ký tự đơn. Backtracking tạo ra đúng một kết quả: ["a","b","c","d"]. Cả hai approach xử lý điều này trivially — pruning không bao giờ loại bỏ nhánh sớm vì không có palindrome đa ký tự nào, nhưng độ sâu recursion là n và chỉ có một leaf.

Toàn bộ chuỗi là palindrome (s = "aba"): dp[0][2] = True. Backtracking giờ có thêm nhánh tại start=0 lấy toàn bộ chuỗi làm một mảnh. Kết quả gồm ["aba"] bên cạnh ["a","b","a"]. Không cần xử lý đặc biệt; bảng DP ghi nhận nó.

Độ dài 2 (s = "aa"): dp[0][1] = True. Kết quả: ["a","a"] và ["aa"]. Hai entries, cả hai đúng.

Bảng so sánh

Với n = 16, sự khác biệt về chi phí kiểm tra palindrome là O(16) vs O(1) mỗi tra cứu. Backtracking vẫn chi phối runtime. Trong thực tế phiên bản DP nhanh hơn vì loại bỏ tính toán lặp lại, nhưng cả hai đều pass thoải mái trong n <= 16.

Tôi sẽ ship cái nào, và tại sao

Tôi sẽ dùng Approach 2 — phiên bản DP tiền xử lý — trong code review thực tế. Lý do không phải tốc độ ở input size này. Mà là sự tách biệt rõ ràng: palindrome oracle được tính một lần, riêng biệt, trước khi search bắt đầu. Ai đọc vòng lặp backtracking không cần nghĩ về cách kiểm tra palindrome — bảng ở đó, tra cứu là thao tác boolean indexing. Code phân tách concerns một cách sạch sẽ.

Approach 1 là điểm khởi đầu đúng để giải thích logic. Nó ngắn hơn, không có bước setup, và làm rõ cấu trúc recursion. Trong phỏng vấn trên bảng trắng tôi có thể viết Approach 1 trước rồi nói "và chúng ta có thể tối ưu bằng cách tiền tính palindromes vào bảng DP 2D để tránh tính lặp."

Bối cảnh duy nhất tôi thích Approach 1 hơn là nếu n nhỏ hơn nhiều và bài toán nằm trong một hệ thống lớn hơn, nơi O(n^2) allocation thêm cho bảng DP có chi phí tôi quan tâm. Với n = 16, đó là tối đa 256 boolean — không đáng kể. Nhưng nguyên tắc là thực: preprocessing có upfront cost, và với input đủ nhỏ, inline check hoàn toàn ổn.

Pattern cốt lõi: choose-explore-unchoose

Cả hai approach đều dùng cùng recursion skeleton chạy xuyên suốt series backtracking này: tại mỗi bước, chọn candidate (một prefix palindrome), explore subproblem từ vị trí mới, rồi unchoose (pop khỏi path). Điều kiện kết thúc là đạt đến cuối chuỗi.

Điều làm Palindrome Partitioning đặc thù là pruning rule: bạn chỉ recurse nếu prefix hiện tại là palindrome. Đây không phải constraint phổ quát như "mỗi phần tử chỉ dùng một lần" (Subsets) hay "thứ tự quan trọng" (Permutations) — đây là bộ lọc content-based trên candidate. DP tiền xử lý chỉ là cách làm bộ lọc đó rẻ hơn.

Mental model có thể chuyển giao: backtracking trên chuỗi là recursion qua các điểm cắt. Bạn đang chọn vị trí cắt nào tiếp theo, và validity check của bạn xác định có theo đuổi nhánh đó không. Bất kỳ bài nào nói "liệt kê tất cả các cách chia chuỗi thoả mãn điều kiện P" đều ánh xạ vào cùng cấu trúc này — thay kiểm tra palindrome bằng bất kỳ kiểm tra P nào cần thiết.

Vị trí trong series backtracking

Series này đã đi qua Subsets, Subsets II, Combination Sum, Combination Sum II, Permutations, và Word Search. Palindrome Partitioning là bài thứ bảy và là bài đầu tiên trong series mà điều kiện rẽ nhánh là một thuộc tính chuỗi không tầm thường thay vì quy tắc set-membership. Decision tree có hình dạng giống Combination Sum — tại mỗi vị trí bạn chọn một mảnh và tiến về phía trước — nhưng điều làm mảnh hợp lệ phong phú hơn.

Palindrome Partitioning II (132) là follow-on tự nhiên: thay vì liệt kê tất cả các partition, tìm số lần cắt tối thiểu để mỗi mảnh là palindrome. Nó bỏ hoàn toàn backtracking và trở thành bài DP thuần túy. Bảng palindrome bạn xây trong Approach 2 ở đây chính xác là những gì bài 132 cũng cần. Nếu bài này đã thoải mái, 132 là bước tiếp theo đúng.

Word Break (139) chia sẻ cùng recursion cut-point nhưng thay "mảnh này có phải palindrome không" bằng "mảnh này có trong từ điển không." Nó hỏi câu trả lời boolean (chuỗi có thể segmented không?) thay vì liệt kê tất cả cách, khiến nó là bài DP 1D thay vì backtracking.

Restore IP Addresses (93) là bài "phân hoạch chuỗi thành các mảnh thoả mãn constraint" khác — đặt ba dấu chấm tại đúng ba vị trí sao cho mỗi segment là một IP octet hợp lệ. Branching factor nhỏ hơn (tối đa 3 ký tự mỗi segment), nhưng skeleton giống hệt.

Letter Combinations of a Phone Number (17) có cùng hình dạng backtracking nhưng làm việc trên mapping (chữ số sang chữ cái) thay vì string split. Cấu trúc đơn giản hơn, nhưng skeleton choose-explore-unchoose là như nhau.