Longest Palindromic Substring

+10

Bạn nhận được một chuỗi s gồm các chữ cái tiếng Anh viết thường. Hãy trả về chuỗi con đối xứng dài nhất: đoạn chữ cái liên tiếp dài nhất đọc xuôi hay ngược đều giống nhau. Nếu có nhiều chuỗi con cùng đạt độ dài lớn nhất, hãy trả về chuỗi bắt đầu ở vị trí xa nhất về bên trái.

Hàm

longestPalindrome(s: string) → string

sstring: chuỗi chữ thường cần tìm kiếm
Trả vềstring: chuỗi con đối xứng dài nhất của s, chuỗi nằm bên trái nhất nếu có nhiều chuỗi cùng độ dài

Ràng buộc

1 ≤ s.length ≤ 2000
s chỉ chứa các chữ cái tiếng Anh viết thường.
Khi có nhiều chuỗi đối xứng cùng có độ dài lớn nhất, đáp án là chuỗi có chỉ số bắt đầu nhỏ nhất.

Ví dụ

Đầu vào: s = "bananas"
Đầu ra: "anana"
Giải thích: "anana" đọc xuôi hay ngược đều giống nhau và có 5 chữ cái. Mọi chuỗi dài hơn đều không khớp ở hai đầu: "banana" (b, a), "ananas" (a, s) và "bananas" (b, s).

Đầu vào: s = "xyzzyabba"
Đầu ra: "yzzy"
Giải thích: "yzzy" và "abba" đều là chuỗi đối xứng có độ dài 4, và không có chuỗi nào dài hơn. "yzzy" bắt đầu ở chỉ số 1, trước "abba" ở chỉ số 5, nên chuỗi này thắng khi hòa.

Đầu vào: s = "abcd"
Đầu ra: "a"
Giải thích: Không có hai chữ cái nào giống nhau, vì vậy mọi chuỗi đối xứng đều chỉ có một chữ cái. Chuỗi đối xứng nằm ngoài cùng bên trái là "a".

Câu hỏi mở rộng

Bạn có thể tìm đáp án trong thời gian O(n) 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

Chuỗi đối xứng (palindrome) đối xứng quanh điểm giữa: với độ dài lẻ, điểm giữa là một chữ cái, như "anana"; với độ dài chẵn, điểm giữa là khoảng trống giữa hai chữ cái giống nhau, như "abba". Mở rộng từng chuỗi đối xứng từ điểm giữa ra ngoài. Mỗi lần so sánh đều mở rộng một chuỗi bạn đã tìm thấy: thời gian O(n²) và bộ nhớ bổ sung O(1), so với O(n³) nếu kiểm tra riêng từng chuỗi con.

Kiểm tra mọi chuỗi con

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Cố định điểm bắt đầu i và điểm kết thúc j, rồi so sánh các chữ cái từ hai đầu vào trong cho đến khi hai chữ cái khác nhau hoặc hai con trỏ gặp nhau. Thử tất cả n(n+1)/2 chuỗi con sẽ không bỏ sót đáp án. Khi xét điểm bắt đầu từ trái sang phải, chỉ thay kết quả tốt nhất khi tìm được chuỗi đối xứng dài hơn hẳn sẽ giữ lại chuỗi nằm bên trái nhất.

Mỗi lần kiểm tra có thể duyệt qua một nửa chuỗi con. Với 2000 bản sao của a, mọi chuỗi con đều là chuỗi đối xứng: khoảng n³/12 ≈ 6.7 × 10^8 lần so sánh chữ cái.

Thuật toán

Bắt đầu với chữ cái đầu tiên là kết quả tốt nhất: bắt đầu ở 0, độ dài là 1.
Với mỗi vị trí bắt đầu i và mỗi vị trí kết thúc j ≥ i, so sánh các chữ cái từ hai đầu tiến về giữa cho đến khi chúng khác nhau hoặc hai con trỏ gặp nhau.
Nếu không có cặp nào khác nhau và j-i+1 lớn hơn độ dài tốt nhất, hãy ghi lại i và độ dài đó.
Trả về chuỗi con bắt đầu ở vị trí tốt nhất và có độ dài tốt nhất.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

Bảng các chuỗi đối xứng theo độ dài

Ý tưởng

Kiểm tra "anana" bằng cách so sánh a với a, rồi n với n, và phép so sánh thứ hai đó chính là toàn bộ phép kiểm tra "nan". Thay vào đó, hãy lưu từng kết quả: s[i..j] là chuỗi đối xứng khi hai đầu trùng nhau và s[i+1..j-1] cũng là chuỗi đối xứng.

Điền bảng pal[i][j] theo độ dài. Các chữ cái đơn là chuỗi đối xứng, hai chữ cái tạo thành chuỗi đối xứng khi chúng trùng nhau, còn một ô dài hơn lấy thông tin từ ô ngắn hơn hai chữ cái đã được điền. Trong "bananas", pal[1][5] đúng vì s[1] và s[5] đều là a, đồng thời pal[2][4] ("nan") cũng đúng. Trong cùng một độ dài, ta xét các vị trí bắt đầu từ trái sang phải, nên chuỗi đối xứng đầu tiên có độ dài kỷ lục sẽ nằm ở vị trí trái nhất.

Khoảng n²/2 ô, mỗi ô cần O(1) thời gian, cho tổng thời gian O(n²). Đổi lại là chi phí bộ nhớ: 4 × 10^6 ô với n = 2000.

Thuật toán

Tạo một bảng n × n pal, tất cả đều là false.
Với mỗi độ dài từ 1 đến n, và mỗi vị trí bắt đầu i sao cho điểm kết thúc j = i+length-1 nằm trong chuỗi, hãy so sánh s[i] và s[j].
Đánh dấu pal[i][j] khi chúng khớp nhau và độ dài không quá 2 hoặc pal[i+1][j-1] là true.
Khi độ dài của một ô được đánh dấu vượt quá độ dài tốt nhất, hãy ghi lại i và độ dài đó.
Trả về chuỗi con bắt đầu tại vị trí tốt nhất.

def longestPalindrome(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)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

Mở rộng quanh mọi tâm

Ý tưởng

Một chuỗi (string) gồm n chữ cái có n tâm chữ cái và n-1 tâm khoảng trống, tổng cộng là 2n-1. Từ một tâm, dịch dần ra ngoài khi hai chữ cái trùng nhau. Gặp cặp chữ cái đầu tiên không trùng nhau hoặc chạm mép thì dừng, vì không thể có chuỗi đối xứng nào dài hơn cùng tâm đó: chuỗi ấy sẽ chứa cặp chữ cái không trùng nhau. Vì vậy, duyệt một lần từ mỗi tâm sẽ tìm được chuỗi đối xứng dài nhất của tâm đó.

Trong "bananas", khi duyệt từ chỉ số 3, n khớp với n và a khớp với a, sau đó dừng ở b và s: độ dài là 5, vị trí bắt đầu là 3 - (5-1)/2 = 1, nên chuỗi là "anana". Hai chuỗi đối xứng có độ dài bằng nhau thì có cùng tính chẵn lẻ, vì vậy tâm nào ở trước thì chuỗi bắt đầu sớm hơn. Duyệt các tâm từ trái sang phải và chỉ thay kết quả tốt nhất khi tìm được độ dài lớn hơn hẳn.

Trường hợp xấu nhất là chuỗi gồm một chữ cái lặp lại: khoảng n²/2 = 2 × 10^6 bước với n = 2000, và chỉ cần vài số nguyên bộ nhớ.

Thuật toán

Viết expand(left, right): khi cả hai chỉ số đều nằm trong chuỗi và các chữ cái trùng nhau, giảm left và tăng right. Trả về right-left-1.
Với mỗi tâm từ 0 đến n-1, lấy giá trị lớn hơn trong expand(center, center) và expand(center, center+1).
Nếu độ dài đó lớn hơn độ dài tốt nhất hiện tại, đặt vị trí bắt đầu tốt nhất thành center - (length-1)/2, làm tròn xuống, và đặt độ dài tốt nhất thành độ dài đó.
Trả về chuỗi con bắt đầu tại vị trí bắt đầu tốt nhất với độ dài tốt nhất.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

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

Chỉ mở rộng quanh các chữ cái sẽ bỏ sót mọi chuỗi palindrome có độ dài chẵn: "abba" trả về "a".
Quá trình duyệt dừng lại sau mỗi đầu mút một bước, nên độ dài là right-left-1. Dùng right-left+1 sẽ tính cả hai chữ cái không khớp.
Thay thế kết quả tốt nhất khi độ dài bằng nhau sẽ trả về chuỗi palindrome nằm bên phải nhất: "abba" thay vì "yzzy" với "xyzzyabba".
Với tâm nằm giữa hai chữ cái, center - length/2 lệch quá một vị trí sang trái. Trong "xyzzyabba", khoảng trống sau chỉ số 2 cho độ dài 4 và vị trí bắt đầu là 2 - (4-1)/2 = 1, không phải 0.
Điền bảng theo vị trí bắt đầu từ 0 trở lên sẽ đọc pal[i+1][j-1] trước khi giá trị này được thiết lập. Hãy điền theo độ dài hoặc duyệt vị trí bắt đầu từ cuối.

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

Độ phức tạp thời gian của bài toán chuỗi con đối xứng dài nhất là gì?

Mở rộng quanh các tâm mất O(n²) thời gian và O(1) bộ nhớ bổ sung. Bảng các chuỗi đối xứng cũng mất O(n²) thời gian nhưng lưu n² ô, còn việc tự kiểm tra từng chuỗi con mất O(n³).

Bạn nên dùng quy hoạch động hay mở rộng từ tâm?

Mở rộng quanh tâm. Cả hai đều tốn thời gian O(n²), nhưng bảng lưu 4 × 10^6 ô với n = 2000, còn cách mở rộng chỉ cần giữ một vài số nguyên. Cách mở rộng cũng dừng lại khi gặp điểm không khớp đầu tiên, vì vậy với chuỗi có ít chuỗi đối xứng, cách này tốn ít hơn nhiều so với n² bước.

Chuỗi con đối xứng dài nhất khác gì với dãy con đối xứng dài nhất?

Chuỗi con là một dãy các chữ cái liên tiếp, còn dãy con có thể bỏ qua chữ cái. Trong "character", chuỗi con đối xứng dài nhất là "ara", nhưng "carac" là một dãy con đối xứng có độ dài 5. Phiên bản dãy con dùng một bảng với (i, j), bỏ đi một đầu khi hai đầu khác nhau.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "bananas"

Đầu ra mong đợi

"anana"

Longest Palindromic Substring

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra mọi chuỗi con

Bảng các chuỗi đối xứng theo độ dài

Mở rộng quanh mọi tâm

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

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

Bài tập tương tự