Chuỗi Palindrome trong PHP sử dụng vòng lặp for

Palindrom là một từ (hoặc một chuỗi ký tự) có thể đọc xuôi hoặc ngược giống hệt nhau. Những ví dụ bao gồm

racecar
madam
mom
level
civic
kayak
rotavator

Logic để xác định một bảng màu rất đơn giản. Lấy đầu vào, đảo ngược nó và sau đó so sánh nó với bản gốc. PHP thậm chí còn có một hoạt động tích hợp sẵn, strrev(), để đảo ngược các chuỗi. Chúng ta có thể viết một hàm để đánh giá xem một chuỗi đầu vào có phải là một palindrome hay không

function determinePalindromeWithReverse($value){
	$reverse = strrev($value);
	if($reverse === $value){
		echo "true \n";
		return true;
	}
        return false;
}

Trong một cuộc phỏng vấn, với vai trò là Kỹ sư phần mềm, tôi đã được hỏi “Cho một chuỗi, hãy xác định xem bạn có thể biến nó thành một bảng màu hay không bằng cách xóa tối đa 1 ký tự. ”

Để giải quyết thách thức đó, tôi có thể lặp qua chuỗi trong khi tăng giá trị của biến đếm. Trên mỗi lần lặp lại, tôi sẽ xóa một ký tự (có chỉ số được xác định bằng số đếm), đảo ngược kết quả và sau đó so sánh nó

function determinePalindromeWithReverseRemoveCharacter($value){
	$reverse = strrev($value);
	if($reverse === $value){
		echo "true \n";
		return true;
	}

	for($i=0;$i<=strlen($value);$i++){
		$first_half = substr($value, 0, $i); // first half of string
		$second_half = substr($value, $i + 1);
		$string_with_one_char_removed = $first_half . $second_half;
		echo "$string_with_one_char_removed \n";
		$reverse = strrev($string_with_one_char_removed);
		if($reverse === $string_with_one_char_removed){
			echo "true \n";
			return true;
		}
	}

}
determinePalindromeWithReverseRemoveCharacter("racecfar"); // true

Tôi sử dụng hàm substr() của PHP để lấy từng nửa của “chuỗi mới đã loại bỏ một ký tự. ” Phép chia đầu tiên bắt đầu từ đầu (chỉ số bằng 0) và tiếp tục cho đến khi bộ đếm xác định vị trí (không ở vòng lặp đầu tiên, một ở vòng lặp thứ hai, v.v.). Phần thứ hai bắt đầu một bước qua số lần lặp lại và kết thúc với phần cuối của chuỗi. Kết quả này là đầu vào ban đầu với một chữ cái đã bị xóa.

Để minh họa cách thức hoạt động của nó, tôi in ra phần nối mỗi lần. Bạn có thể thấy rằng chương trình tiếp tục cho đến khi kết quả là một bảng màu

Mặc dù điều này hoạt động, nhưng việc đảo ngược chuỗi mỗi lần rất tốn kém. Nó làm giảm hiệu quả thuật toán, khiến giải pháp “không thể mở rộng. ” Làm thế nào chúng ta có thể quyết định xem một chuỗi có phải là một palindrome hay không mà không đảo ngược nó?

Xác thực một bảng màu bằng cách sử dụng đệ quy

Đánh giá một chuỗi là một bảng màu có thể được thực hiện bằng cách sử dụng đệ quy. Trong lập trình, đệ quy là khi một hàm gọi chính nó

Trước khi chúng tôi lo lắng về việc xóa bất kỳ ký tự nào như chúng tôi đã làm ở trên, chúng tôi cần một chức năng mới để xác minh một bảng màu mà không đảo ngược nó

function determinePalindromeRecursively($value){
    if ((strlen($value) < 2)){
        // echo "true \n";
        return true;
    }else{
        if (substr($value,0,1) == substr($value,(strlen($value) - 1),1)){
            echo substr($value,1,strlen($value) - 2) . "\n";
            return determinePalindromeRecursively(substr($value,1,strlen($value) -2));
        }else{
            // echo " Not a Palindrome"; 
            return false;
        }
    }
}

Phương pháp này so sánh các ký tự đầu tiên và cuối cùng của đầu vào. Nếu chúng khớp nhau, mã của chúng tôi sẽ xóa chúng và chuyển giá trị $value được cập nhật trở lại chính nó theo cách đệ quy. Điều này tiếp tục cho đến khi chúng ta đi xuống một chữ cái hoặc ít hơn – khi chúng ta biết rằng chuỗi ban đầu là một bảng màu

Để lấy ký tự đầu tiên, chúng ta yêu cầu phương thức substr() lấy giá trị $, bắt đầu từ đầu (chỉ số bằng 0) và thu thập một phần tử. chất nền($value,0,1)

Để lấy ký tự cuối cùng, chúng ta yêu cầu phương thức substr() lấy giá trị $, bắt đầu từ cuối (độ dài của chuỗi trừ đi một) và thu thập một phần tử. chất nền($value,(strlen($value) – 1),1)

Để xóa cả chữ cái đầu tiên và chữ cái cuối cùng, chúng tôi yêu cầu substr() bắt đầu chỉ qua phần tử đầu tiên (được biểu thị bằng chỉ số 1) và thu thập các ký tự có giá trị độ dài của chuỗi trừ đi hai

Lưu ý rằng trên mỗi vòng lặp đệ quy, chuỗi sẽ mất các ký hiệu phía trước và phía sau

Bây giờ, hãy nhớ thử thách ban đầu. “Cho một chuỗi, hãy xác định xem bạn có thể biến nó thành một bảng màu nhạt hay không bằng cách xóa tối đa 1 ký tự. ”

Tất cả những gì còn lại là sử dụng hàm đệ quy của chúng tôi song song với việc xóa một ký tự trên mỗi vòng lặp

function determinePalindromeRecursively($value){
    if ((strlen($value) < 2)){
        // echo "true \n";
        return true;
    }else{
        if (substr($value,0,1) == substr($value,(strlen($value) - 1),1)){
            echo substr($value,1,strlen($value) -2) . "\n";
            return determinePalindromeRecursively(substr($value,1,strlen($value) -2));
        }else{
            // echo " Not a Palindrome"; 
            return false;
        }
    }
}

function determinePalindromeRecursivelyWhileRemovingOneCharacter($value){

    for($i=0;$i<=strlen($value);$i++){
        $first_half = substr($value, 0, $i); // first half of string
        $second_half = substr($value, $i + 1);
        $string_with_one_char_removed = $first_half . $second_half;
        // echo "$string_with_one_char_removed \n";
         
        if(determinePalindromeRecursively($string_with_one_char_removed)){
            echo "true \n";
            return true;
        }
    }
    echo "false \n";
    return false;

}

determinePalindromeRecursivelyWhileRemovingOneCharacter("racecadr");

Hãy dùng thử, cấu trúc lại mã của tôi và xem liệu bạn có thể giải quyết vấn đề này theo cách khác không. Có những câu đố khoa học máy tính khác về palindrome mà bạn có thể áp dụng logic này vào. Chúc vui vẻ

Làm cách nào để tìm chuỗi palindrome trong PHP?

Cần bao nhiêu vòng lặp để kiểm tra chuỗi có màu nhạt trong PHP không?

Làm thế nào để viết chương trình palindrome trong PHP?