Bài tập Palindrome

Palindrome hay còn gọi là xâu đối xứng, xâu đối gương là tên gọi của những xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. VD: MADAM, IOI,… Nhờ tính chất đặc biệt đó mà có khá nhiều bài tập có liên quan đến Palindrome, phần lớn trong chúng thường đi kèm với QHĐ. Tôi xin giới thiệu với các bạn một vài bài tập như vậy.

Bài 1: Kiểm tra Palindrome

Bài toán: Cho 1 xâu. Kiểm tra nó có phải là Palindrome hay không?

Đây là một bài cơ bản, nhưng quan trọng vì nó được đề cập đến trong nhiều bài tập khác. Cách làm tốt nhất là duyệt đơn thuần mất O(N)O(N).

Ý tưởng:

  • Chạy vòng lập với độ dài bằng một nữa chuỗi
  • So sánh đối xứng lần lượt vị trí đầu và cuối chuỗi
function is_polindrome($str){
    $length = strlen($str);
    for($i = 1; $i<= $length/2; $i++){
        if($str[$i-1]!= $str[$length-$i])
            return false; 
    }
    return true;
}
echo is_polindrome('a28082a'); 
// result: 1

Một số palindrome thú vị:

Leave a Reply

Your email address will not be published. Required fields are marked *

Blogs © 2018 Frontier Theme