Palindrome Partitioning

Q: Độ phức tạp thời gian của bài toán phân hoạch chuỗi đối xứng là bao nhiêu?

Với một chuỗi gồm các chữ cái giống nhau, cả 2^(n-1) cách tách đều là lời giải, mỗi lời giải dài tối đa 2n-1 ký tự: O(n × 2^n) . Không có phương pháp nào nhanh hơn, vì việc ghi lời giải cũng tốn chừng ấy thời gian. Bảng palindrome cần thêm thời gian và bộ nhớ O(n²) , còn đệ quy cần O(n) .

Q: Một chuỗi có thể có bao nhiêu cách phân đoạn thành chuỗi đối xứng?

Tối đa là 2^(n-1) , tương ứng với mỗi cách chọn các khoảng trống trong số n-1 khoảng trống để cắt. Chuỗi gồm các chữ cái giống nhau đạt đến giới hạn đó: 1.024 cách chia với 11 chữ cái. Chuỗi không có chữ cái nào lặp lại chỉ có một cách chia, mỗi chữ cái đứng riêng.

Q: Phân hoạch chuỗi đối xứng là quy hoạch động hay quay lui?

Nó sử dụng cả hai. Liệt kê tối đa 2^(n-1) cách chia đòi hỏi một quá trình tìm kiếm xây dựng từng phần chia một: quay lui. Quy hoạch động tạo bảng có hoặc không cho biết các chuỗi con đối xứng mà quá trình tìm kiếm đọc, và điền bảng một lần trong O(n²) .

Trung bìnhQuay lui Quy hoạch động

+10

Chuỗi đối xứng đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Chia chuỗi s thành một hoặc nhiều phần sao cho mỗi phần đều là chuỗi đối xứng, rồi trả về mọi cách chia.

Viết mỗi cách chia bằng các phần theo thứ tự, nối với nhau bằng |: chia aab thành a, a và b thì được a|a|b. Trả về các cách chia theo thứ tự tăng dần, so sánh mã ký tự, vì vậy | đứng sau mọi chữ cái viết thường.

Hàm

partition(s: string) → string-array

sstring: chuỗi chữ cái viết thường cần cắt
Trả vềstring-array: mọi cách phân tách s thành các chuỗi đối xứng, viết các phần cách nhau bằng |, theo thứ tự tăng dần

Ràng buộc

1 ≤ s.length ≤ 11
s chỉ chứa các chữ cái tiếng Anh viết thường.
Một chuỗi gồm 11 chữ cái giống nhau có 1.024 cách tách, nhiều nhất.

Ví dụ

Đầu vào: s = "aab"
Đầu ra: ["aa|b", "a|a|b"]
Giải thích: Chỉ aa|b và a|a|b có tất cả các phần là chuỗi đối xứng (palindrome); a|ab không đạt vì ab không phải chuỗi đối xứng. aa|b xếp trước: ở ký tự thứ hai, nó có a, còn cách kia có |, ký tự này xếp sau mọi chữ cái.

Đầu vào: s = "abba"
Đầu ra: ["abba", "a|bb|a", "a|b|b|a"]
Giải thích: abba tự nó là một chuỗi đối xứng, vì vậy chuỗi chưa bị cắt là một cách chia và được sắp xếp trước: ký tự thứ hai của nó là một chữ cái. a|bb|a đứng trước a|b|b|a: ở ký tự thứ tư, nó có b, còn chuỗi kia có |.

Câu hỏi mở rộng

Bạn có thể tìm số lần cắt ít nhất để chia s thành các chuỗi đối xứng với độ dài tối đa 2.000 không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi khoảng trống trong số n-1 khoảng giữa các chữ cái có thể được cắt hoặc không, nên có 2^(n-1) cách phân tách, và tất cả đều có thể là đáp án. Bạn không thể giảm kích thước đầu ra, nhưng có thể bỏ qua những cách phân tách không hợp lệ: tạo từng cách từ trái sang phải, chỉ cắt các đoạn đối xứng và tra cứu tính đối xứng trong một bảng đã điền sẵn.

Thử mọi tập hợp các đường cắt

Ý tưởng

Đánh số các cách tách bằng số nguyên từ 0 đến 2^(n-1)-1, mỗi bit cho biết có cắt tại một khoảng trống hay không. Giữ lại một số nếu mọi phần đều là chuỗi đối xứng.

Nếu khoảng trống đầu tiên ứng với bit cao nhất, đếm tăng dần sẽ liệt kê các cách tách theo thứ tự tăng dần. Với hai số, bit cao nhất tại vị trí chúng khác nhau ứng với khoảng trống sớm nhất mà một số cắt còn số kia thì không. Trước vị trí đó, các chuỗi giống nhau; tại đó, số nhỏ hơn có một chữ cái còn số lớn hơn có |, ký tự này xếp sau mọi chữ cái. Với aab, số 1 cho aa|b và số 3 cho a|a|b.

Với 11 chữ cái, ta có 1.024 mặt nạ, mỗi mặt nạ gồm 11 chữ cái. Phần lãng phí nằm ở những cách tách bị loại: abcdefghijk tạo ra cả 1.024 cách để tìm một đáp án.

Thuật toán

Duyệt vòng lặp mask từ 0 đến 2^(n-1)-1.
Duyệt các chữ cái; kết thúc một phần sau chữ cái i khi i là chỉ số cuối cùng hoặc bit n-2-i của mask được bật.
Kiểm tra từng phần bằng hai con trỏ di chuyển vào trong.
Nếu mọi phần đều là chuỗi đối xứng, nối các phần bằng | rồi thêm chuỗi đó vào đáp án.
Trả về đáp án; đáp án đã được sắp xếp vì khoảng ngắt đầu tiên là bit cao nhất.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

Quay lui với bảng palindrome

Ý tưởng

Phần đầu tiên là một tiền tố đối xứng s[0..end], còn việc chia phần còn lại chính là bài toán tương tự bắt đầu từ end+1. Vì vậy, backtrack(start) thử mọi end sao cho s[start..end] là chuỗi đối xứng, thêm phần đó, gọi đệ quy rồi xóa phần đó. Mỗi nhánh đều kết thúc bằng một đáp án, vì một ký tự đơn lẻ là chuỗi đối xứng, nên khối lượng công việc phụ thuộc vào kích thước đầu ra: với abcdefghijk, quá trình tìm kiếm chỉ đi theo một đường.

Điều kiện s[start..end] có phải là chuỗi đối xứng hay không xuất hiện ở nhiều nhánh, nên hãy tra cứu trong một bảng: s[i..j] bằng một khi s[i] == s[j] và phần bên trong s[i+1..j-1] bằng một, hoặc khi phần đó có nhiều nhất 2 ký tự.

Thử end từ chỉ số cuối trở về trước sẽ tạo ra đầu ra đã sắp xếp. Hai cách chia có phần đầu tiên khác nhau sẽ giống nhau cho đến hết phần ngắn hơn; tại đó, phần ngắn hơn có | còn phần dài hơn có một ký tự, nên phần đầu tiên dài hơn được xếp trước.

Thuật toán

Điền pal[i][j] với i chạy từ n-1 xuống 0: s[i] == s[j] và một trong hai điều kiện sau đúng: j-i < 2 hoặc pal[i+1][j-1].
Viết backtrack(start). Nếu start bằng n, ghép các phần hiện tại bằng | rồi lưu chuỗi.
Nếu không, lặp end từ n-1 xuống start, và bỏ qua giá trị đó nếu pal[start][end] không đúng.
Thêm s[start..end] vào các phần, gọi backtrack(end+1), rồi xóa phần đó.
Gọi backtrack(0) và trả về các cách tách đã lưu, vốn đã được sắp xếp.

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways.
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

Lỗi thường gặp và trường hợp biên

Thử phần ngắn nhất trước. Các phần được tách đúng nhưng sai thứ tự: a|a|b đứng trước aa|b.
Sắp xếp ở cuối bằng phép so sánh tuân theo quy tắc ngôn ngữ hoặc vùng miền, có thể khiến | đứng trước các chữ cái. Hãy so sánh mã ký tự hoặc tạo các cách tách theo đúng thứ tự.
Điền bảng palindrome khi i tăng dần. Khi đó, pal[i+1][j-1] được đọc trước khi tính xong; hãy điền i từ n-1 giảm dần.
Nhầm lẫn giữa end bao gồm ký tự cuối và điểm kết thúc chuỗi con không bao gồm ký tự cuối. Phần s[start..end] có end-start+1 chữ cái.
Lưu danh sách các phần dùng chung thay vì chuỗi đã nối. Quá trình tìm kiếm liên tục thay đổi danh sách đó, nên mọi mục đã lưu đều trở nên giống nhau.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán phân hoạch chuỗi đối xứng là bao nhiêu?

Với một chuỗi gồm các chữ cái giống nhau, cả 2^(n-1) cách tách đều là lời giải, mỗi lời giải dài tối đa 2n-1 ký tự: O(n × 2^n). Không có phương pháp nào nhanh hơn, vì việc ghi lời giải cũng tốn chừng ấy thời gian. Bảng palindrome cần thêm thời gian và bộ nhớ O(n²), còn đệ quy cần O(n).

Một chuỗi có thể có bao nhiêu cách phân đoạn thành chuỗi đối xứng?

Tối đa là 2^(n-1), tương ứng với mỗi cách chọn các khoảng trống trong số n-1 khoảng trống để cắt. Chuỗi gồm các chữ cái giống nhau đạt đến giới hạn đó: 1.024 cách chia với 11 chữ cái. Chuỗi không có chữ cái nào lặp lại chỉ có một cách chia, mỗi chữ cái đứng riêng.

Phân hoạch chuỗi đối xứng là quy hoạch động hay quay lui?

Nó sử dụng cả hai. Liệt kê tối đa 2^(n-1) cách chia đòi hỏi một quá trình tìm kiếm xây dựng từng phần chia một: quay lui. Quy hoạch động tạo bảng có hoặc không cho biết các chuỗi con đối xứng mà quá trình tìm kiếm đọc, và điền bảng một lần trong O(n²).

def partition(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

s = "aab"

Đầu ra mong đợi

["aa|b", "a|a|b"]