Valid Palindrome

Q: Độ phức tạp thời gian của Valid Palindrome là bao nhiêu?

Cả hai cách đều chạy trong thời gian O(n) , vì mỗi ký tự được xem xét một số lần cố định. Cách làm sạch trước dùng thêm bộ nhớ O(n) để lưu bản sao. Phiên bản dùng hai con trỏ chỉ dùng thêm bộ nhớ O(1) , vì chỉ giữ hai chỉ số.

Q: Chuỗi rỗng có phải là chuỗi đối xứng không?

Đúng vậy. Chuỗi rỗng đọc theo cả hai chiều đều giống nhau, nên một chuỗi như ?!-_ , có tất cả ký tự đều bị bỏ qua, sẽ trả về true . Cả hai cách đều xử lý được điều này mà không cần thêm code: chuỗi đã làm sạch bằng với chuỗi đảo ngược rỗng của nó, và hai con trỏ không bao giờ tìm thấy cặp nào khác nhau.

Q: Tại sao dùng hai con trỏ thay vì đảo ngược chuỗi?

Đảo ngược cần một bản sao đã làm sạch và một bản sao đã đảo ngược, tiêu tốn thêm bộ nhớ O(n) . Hai con trỏ so sánh từng cặp tương ứng ngay tại chỗ và dừng ở điểm không khớp đầu tiên, thường chỉ sau vài bước.

DễHai con trỏ

+10

Bạn nhận được một chuỗi s. Chỉ giữ lại chữ cái và chữ số, xem chữ hoa và chữ thường là cùng một chữ cái, rồi xác định xem phần còn lại đọc từ trái sang phải có giống như khi đọc từ phải sang trái không. Trả về true nếu có, nếu không thì trả về false.

Bỏ qua mọi ký tự khác, chẳng hạn như ., !, ?, :, ;, - hoặc _. Nếu s không có chữ cái hay chữ số nào, sẽ không còn gì cả, và một văn bản rỗng được xem là một chuỗi đối xứng.

Hàm

isPalindrome(s: string) → boolean

sstring: văn bản cần kiểm tra, bao gồm cả dấu câu
Trả vềboolean: đúng nếu các chữ cái và chữ số trong s đọc giống nhau theo cả hai chiều, không phân biệt chữ hoa chữ thường

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chứa các chữ cái tiếng Anh, chữ số và dấu câu . ! ? : ; - _, không có khoảng trắng.

Ví dụ

Đầu vào: s = "Was_it_a_car_or_a_cat_I_saw?"
Đầu ra: true
Giải thích: Bỏ các dấu gạch dưới và dấu chấm hỏi, rồi đổi các chữ in hoa thành chữ thường: bạn sẽ được wasitacaroracatisaw, đọc ngược lại vẫn giống như vậy.

Đầu vào: s = "race-a-car"
Đầu ra: false
Giải thích: Nếu bỏ các dấu gạch nối, văn bản sẽ là raceacar. Chữ e ở giữa có chữ a làm ký tự đối xứng, nên đáp án là false.

Đầu vào: s = "Step-on-no-pets!"
Đầu ra: true
Giải thích: Văn bản được giữ lại là steponnopets. Chữ hoa S khớp với chữ thường s ở cuối vì không phân biệt chữ hoa chữ thường, còn dấu gạch nối và ! không ảnh hưởng.

Câu hỏi mở rộng

Bạn có thể xác định điều đó với bộ nhớ bổ sung O(1) mà không tạo bản sao đã làm sạch của s 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

Phép kiểm tra vẫn như thường lệ: ký tự đầu tiên được giữ lại phải bằng ký tự cuối cùng, ký tự thứ hai phải bằng ký tự áp chót, cứ tiếp tục như vậy. Điểm khó là các ký tự được giữ lại không nằm ở những chỉ số đối xứng trong s, vì dấu câu phân bố không đều. Hãy xóa dấu câu trước, hoặc để hai con trỏ bỏ qua chúng khi tiến dần vào giữa.

Làm sạch chuỗi, sau đó so sánh chuỗi đó với phiên bản đảo ngược

Ý tưởng

Duyệt qua s, giữ lại từng chữ cái hoặc chữ số ở dạng chữ thường và bỏ qua phần còn lại: Step-on-no-pets! trở thành steponnopets. Việc làm sạch sẽ xóa chính xác những gì đề bài yêu cầu bỏ qua, vì vậy câu trả lời là liệu văn bản này có bằng văn bản đảo ngược của nó hay không. Chuỗi không có chữ cái hoặc chữ số sẽ được làm sạch thành văn bản rỗng, và văn bản này bằng văn bản đảo ngược của nó mà không cần trường hợp đặc biệt.

Độ phức tạp thời gian là O(n), còn bản sao và bản đảo ngược của nó cần thêm O(n) bộ nhớ.

Thuật toán

Tạo một chuỗi rỗng cleaned.
Với mỗi ký tự trong s, nếu đó là chữ cái hoặc chữ số, hãy thêm ký tự đó ở dạng chữ thường.
Đảo ngược cleaned.
Trả về kết quả cho biết cleaned có bằng phiên bản đảo ngược của nó hay không.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Hai con trỏ bỏ qua dấu câu

Ý tưởng

Bản sao đã làm sạch chỉ dùng để so sánh các ký tự đối xứng, và bạn có thể so sánh trực tiếp trên s. Di chuyển từng con trỏ qua dấu câu, rồi so sánh hai ký tự ở dạng chữ thường. Các con trỏ luôn dừng ở ký tự tiếp theo được giữ lại ở mỗi đầu, nên chúng lần lượt duyệt qua các cặp (ký tự được giữ lại đầu tiên, ký tự được giữ lại cuối cùng), (ký tự được giữ lại thứ hai, ký tự được giữ lại áp chót) và cứ tiếp tục như vậy: chính xác là các cặp mà phép so sánh ngược kiểm tra.

Mỗi bước di chuyển ít nhất một con trỏ, vì vậy vòng lặp chạy tối đa n lần và chỉ lưu hai chỉ số. Vòng lặp cũng dừng ở điểm không khớp đầu tiên: Abc-dcbX cho kết quả false sau khi so sánh A với X.

Thuật toán

Đặt left = 0 và right = n-1.
Khi left < right: nếu s[left] không phải là chữ cái hoặc chữ số, tăng left rồi tiếp tục.
Nếu không, nếu s[right] không phải là chữ cái hoặc chữ số, giảm right rồi tiếp tục.
Nếu không, hãy so sánh hai ký tự ở dạng chữ thường. Nếu chúng khác nhau, trả về false; nếu chúng giống nhau, di chuyển cả hai con trỏ vào phía trong.
Khi hai con trỏ gặp nhau, trả về true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

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

So sánh s[i] với s[n-1-i] trên chuỗi thô. a-ba là chuỗi đối xứng sau khi bỏ dấu gạch nối, nhưng ký tự đối xứng với - ở chỉ số 1 trong chuỗi thô là b ở chỉ số 2.
Di chuyển cả hai con trỏ khi chỉ một con trỏ nằm trên dấu câu. Hãy bỏ qua từng bên một, nếu không hai bên sẽ lệch nhau.
Bỏ qua dấu câu trong vòng lặp bên trong mà không kiểm tra left < right. Với ?!-_, vòng lặp sẽ chạy vượt quá cuối chuỗi.
Coi chữ số là ký tự không cần quan tâm. 0P là false: 0 vẫn được giữ lại và nó không phải chữ cái p.
Trong PHP và R, một chuỗi chữ số như 12321 có thể được chuyển thành số. Trước tiên, hãy chuyển nó thành chuỗi.

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

Độ phức tạp thời gian của Valid Palindrome là bao nhiêu?

Cả hai cách đều chạy trong thời gian O(n), vì mỗi ký tự được xem xét một số lần cố định. Cách làm sạch trước dùng thêm bộ nhớ O(n) để lưu bản sao. Phiên bản dùng hai con trỏ chỉ dùng thêm bộ nhớ O(1), vì chỉ giữ hai chỉ số.

Chuỗi rỗng có phải là chuỗi đối xứng không?

Đúng vậy. Chuỗi rỗng đọc theo cả hai chiều đều giống nhau, nên một chuỗi như ?!-_, có tất cả ký tự đều bị bỏ qua, sẽ trả về true. Cả hai cách đều xử lý được điều này mà không cần thêm code: chuỗi đã làm sạch bằng với chuỗi đảo ngược rỗng của nó, và hai con trỏ không bao giờ tìm thấy cặp nào khác nhau.

Tại sao dùng hai con trỏ thay vì đảo ngược chuỗi?

Đảo ngược cần một bản sao đã làm sạch và một bản sao đã đảo ngược, tiêu tốn thêm bộ nhớ O(n). Hai con trỏ so sánh từng cặp tương ứng ngay tại chỗ và dừng ở điểm không khớp đầu tiên, thường chỉ sau vài bước.

def isPalindrome(s):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "Was_it_a_car_or_a_cat_I_saw?"

Đầu ra mong đợi

true