Palindrome String

Q: Làm thế nào để kiểm tra một chuỗi có phải là chuỗi đối xứng không?

So sánh ký tự đầu tiên với ký tự cuối cùng, ký tự thứ hai với ký tự áp chót, rồi tiếp tục như vậy về phía giữa. Nếu bất kỳ cặp nào khác nhau, chuỗi đó không phải là chuỗi đối xứng. Hai chỉ số bắt đầu ở hai đầu và di chuyển vào trong sẽ thực hiện việc này chỉ trong một lượt duyệt.

Q: Bạn có thể kiểm tra một chuỗi đối xứng mà không cần thêm bộ nhớ không?

Có. Cách kiểm tra bằng hai con trỏ đọc trực tiếp các ký tự và lưu hai chỉ số, nên chỉ dùng thêm O(1) dung lượng. So sánh s với chuỗi đảo ngược của nó thì viết ngắn hơn, nhưng tạo thêm một chuỗi gồm n ký tự.

Q: Độ phức tạp thời gian khi kiểm tra một chuỗi đối xứng là bao nhiêu?

O(n) cho chuỗi có độ dài n . Phép kiểm tra bằng hai con trỏ thực hiện nhiều nhất n / 2 phép so sánh và dừng ở điểm không khớp đầu tiên, vì vậy coddy chỉ cần một phép so sánh.

Q: Một ký tự có phải là chuỗi palindrome không?

Đúng vậy, đọc theo cả hai chiều đều giống nhau. Trong vòng lặp hai con trỏ, left và right đều bắt đầu ở chỉ số 0, vòng lặp không chạy lần nào và hàm trả về true .

Người mớiHai con trỏ Mảng và chuỗi

+10

Một chuỗi là đối xứng khi đọc từ trái sang phải hay từ phải sang trái đều giống nhau, như level. Hãy viết một hàm (function) nhận chuỗi s gồm các chữ cái tiếng Anh viết thường và trả về true nếu s là chuỗi đối xứng, nếu không thì trả về false.

Hàm

isPalindrome(s: string) → boolean

sstring: chuỗi chữ thường cần kiểm tra
Trả vềboolean: đúng khi đọc s theo cả hai chiều đều giống nhau

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh viết thường (a đến z).

Ví dụ

Đầu vào: s = "racecar"
Đầu ra: true
Giải thích: So sánh từ ngoài vào trong: r với r, a với a, c với c. Ký tự e ở giữa không có ký tự ghép cặp và cũng không cần, nên đáp án là true.

Đầu vào: s = "abba"
Đầu ra: true
Giải thích: Với độ dài chẵn, mỗi chữ cái đều có một chữ cái ghép cặp: hai chữ a khớp với nhau và hai chữ b khớp với nhau, nên đáp án là true.

Đầu vào: s = "coddy"
Đầu ra: false
Giải thích: Chữ cái đầu tiên c và chữ cái cuối cùng y đã khác nhau, nên coddy không phải là palindrome và kết quả là false.

Câu hỏi mở rộng

Bạn sẽ thay đổi hai con trỏ như thế nào để bỏ qua khoảng trắng và dấu câu, đồng thời không phân biệt chữ hoa chữ thường, để Was it a car or a cat I saw được tính là một chuỗi palindrome?

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ột chuỗi đối xứng giống với chính nó khi đảo ngược, vì vậy bạn có thể tạo chuỗi đảo ngược rồi so sánh. Bạn không cần tạo bản sao: ký tự đầu tiên phải khớp với ký tự cuối cùng, ký tự thứ hai phải khớp với ký tự áp chót, cứ thế tiếp tục. Hai chỉ số di chuyển vào giữa sẽ kiểm tra các cặp ký tự ngay tại chỗ và dừng ở điểm không khớp đầu tiên.

So sánh chuỗi với phiên bản đảo ngược của nó

Ý tưởng

Đảo ngược s rồi so sánh: khi đảo ngược racecar, ta được racecar, còn khi đảo ngược coddy, ta được yddoc. Một chuỗi đọc xuôi hay ngược đều giống nhau khi và chỉ khi nó bằng chính phiên bản đảo ngược của nó.

Độ phức tạp thời gian là O(n), nhưng bản sao đã đảo ngược cần thêm O(n) bộ nhớ, tức 50,000 ký tự khi n = 5 × 10^4. Cách này cũng luôn xử lý toàn bộ chuỗi: chỉ cần nhìn ký tự đầu và cuối là có thể kết luận coddy, vậy mà cả năm ký tự vẫn bị đảo ngược trước.

Thuật toán

Tạo chuỗi đảo ngược của s bằng hàm đảo ngược của ngôn ngữ hoặc dùng vòng lặp từ ký tự cuối cùng đến ký tự đầu tiên.
So sánh chuỗi đảo ngược với s.
Trả về true nếu chúng bằng nhau và false nếu không.

def isPalindrome(s):
    return s == s[::-1]

Hai con trỏ từ hai đầu

Ý tưởng

Đảo ngược chuyển chỉ số i thành chỉ số n-1-i, vì vậy s bằng chính chuỗi đảo ngược khi và chỉ khi s[i] bằng s[n-1-i] với mọi i. Mỗi cặp xuất hiện hai lần trong điều kiện đó, nên chỉ cần kiểm tra nửa bên trái. Trong racecar, các cặp là (0, 6), (1, 5) và (2, 4); ký tự e ở giữa, tại chỉ số 3, không cần cặp tương ứng.

Cặp đầu tiên khác nhau chứng minh đáp án là false, nên chỉ cần một phép so sánh là xác định được kết quả của coddy. Cần thực hiện nhiều nhất n / 2 phép so sánh, mất thời gian O(n), còn hai chỉ số cần không gian O(1). R trước tiên đọc chuỗi thành một vector mã ký tự, việc này mất O(n).

Thuật toán

Đặt left = 0 và right = n-1.
Khi left < right, hãy so sánh s[left] với s[right].
Nếu chúng khác nhau, trả về false.
Nếu không, tăng left lên 1, giảm right đi 1 rồi lặp lại.
Khi hai con trỏ gặp nhau hoặc vượt qua nhau, mọi cặp đều khớp: trả về true.

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

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

Trả về true ngay khi một cặp khớp. abca vượt qua cặp bên ngoài nhưng không vượt qua cặp bên trong, vì vậy chỉ trả về true sau vòng lặp.
Bắt đầu right ở n thay vì n-1, khiến chương trình đọc vượt quá cuối chuỗi (trong C, ký tự kết thúc '\0'). Trong Lua và R, chỉ số bắt đầu từ 1 đến n, vì vậy ở đó right bắt đầu ở n.
So sánh chuỗi bằng == trong C. reversed == s so sánh hai con trỏ và cho kết quả false khi so sánh với một bản sao; hãy dùng strcmp.
Tạo chuỗi đảo ngược bằng result = result + ch. Mỗi bước sao chép toàn bộ chuỗi hiện có: khoảng 1.25 × 10^9 lượt sao chép ký tự cho 50,000 chữ cái.
Dùng số nguyên làm chỉ số cho chuỗi Swift: cách này không biên dịch được. Hãy duyệt qua s.utf8 hoặc sao chép các ký tự vào một mảng.

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

Làm thế nào để kiểm tra một chuỗi có phải là chuỗi đối xứng không?

So sánh ký tự đầu tiên với ký tự cuối cùng, ký tự thứ hai với ký tự áp chót, rồi tiếp tục như vậy về phía giữa. Nếu bất kỳ cặp nào khác nhau, chuỗi đó không phải là chuỗi đối xứng. Hai chỉ số bắt đầu ở hai đầu và di chuyển vào trong sẽ thực hiện việc này chỉ trong một lượt duyệt.

Bạn có thể kiểm tra một chuỗi đối xứng mà không cần thêm bộ nhớ không?

Có. Cách kiểm tra bằng hai con trỏ đọc trực tiếp các ký tự và lưu hai chỉ số, nên chỉ dùng thêm O(1) dung lượng. So sánh s với chuỗi đảo ngược của nó thì viết ngắn hơn, nhưng tạo thêm một chuỗi gồm n ký tự.

Độ phức tạp thời gian khi kiểm tra một chuỗi đối xứng là bao nhiêu?

O(n) cho chuỗi có độ dài n. Phép kiểm tra bằng hai con trỏ thực hiện nhiều nhất n / 2 phép so sánh và dừng ở điểm không khớp đầu tiên, vì vậy coddy chỉ cần một phép so sánh.

Một ký tự có phải là chuỗi palindrome không?

Đúng vậy, đọc theo cả hai chiều đều giống nhau. Trong vòng lặp hai con trỏ, left và right đều bắt đầu ở chỉ số 0, vòng lặp không chạy lần nào và hàm trả về true.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "racecar"

Đầu ra mong đợi

true