我正在编写一个能够识别回文的脚本(出于乐趣)。到目前为止，我成功地使用了"Kayak"、"Racecar"、"Anna"、"A man A plan A canal Panama"等词，但后一个短语的变体，如"amanplana canalpan ama"，却给我带来了问题。
作为旁注:我确实明白使用PCRE会使事情对我来说容易得多，但我对它并不流利，我的主要目标之一是理解检查回文背后的算法。
<?php
$word = "amanaplana canalpan ama";
$space = " ";
$word_smallcase = strtolower($word);
$word_array = str_split($word_smallcase);
if(in_array($space, $word_array)){
for($m = 0; $m<count($word_array); $m = $m + 1){
if($word_array[$m] == $space)
unset($word_array[$m]);
}
}
$count = 0;
$scan_count = -1;
for($i = 0; $i < (count($word_array)/2); $i = $i + 1){
for($j = count($word_array); $j > (count($word_array)/2); $j = $j - 1){
if($word_array[$i]==$word_array[$j]){
$count = $count + 1;
break;
}
}
$scan_count = $scan_count + 1;
}
if ($count == $scan_count){
echo $word." is a palindrome";
}
else{
echo $word ." is NOT a palindrome";
}
?>
请回复:
- 识别我患有的bug。
- 建议我怎么可能改进代码(我会很高兴，如果我可以不需要使用$count或$scan_count就可以工作我的眼睛，相对业余)。
目前，您是在逐字测试的基础上进行测试的，如果单词在整个回文中不均匀，这肯定会导致错误。
在PHP中查看字符串是否为重复字符串的简单方法:
$test = str_replace( array(',', '.', ' '
//, and any other punctuation you aren't using
), '', $input );
$test = strtolower( $test );
echo $input . ' is ' .
( ( strrev( $test ) == $test )? "": "not " )
' palandromic.';
至于你的代码:遍历数组并同时删除一些东西是自找麻烦。您最好使用str_replace。如果没有这个选项，我会使用:
// this takes more space, but it is easier to understand.
$tmp = array();
for($m = 0; $m<count($word_array); $m++){ // ++ is the same as $m = $m + 1
if($word_array[$m] != $space)
$tmp[] = $word_array[$m];
}
$word_array = $tmp;
如果strrev(反转字符串)不可用:
$l = count( $word_array ) / 2; // cache this, no sense in recounting
$is_palindromic = TRUE;
for( $i = 0; $i < $l; $i++ )
{
if( $word_array[ $i ] != $word_array[ ( -1 - $i ) ] )
{
$is_palindromic = FALSE;
break;
}
}
echo $input . ' is ' .
( $is_palindromic )? "": "not " )
' palandromic.';
这里发生了一些事情…
首先，我不确定你是否意识到unset 'ing数组实际上并没有删除索引:
$array = array(0, 1, 2, 3);
unset($array[2]);
var_dump($array);
/* array(3) {
[0]=>
int(0)
[1]=>
int(1)
[3]=>
int(3)
} */
当你遍历数组中的元素时你会有一些未定义的偏移。要一个一个地走，你应该使用foreach回路控制。
另一个问题在于这里嵌套的for循环:
for($i = 0; $i < (count($word_array)/2); $i = $i + 1){
for($j = count($word_array); $j > (count($word_array)/2); $j = $j - 1){
给定"amanaplanacanalpanama"，看看你在做什么:
比较，一步一步地(顺便说一句，你在$j的初始化项上偏离了1…$word_array[count($word_array)]指向的是巴拿马的"m"，而不是"a"):
a eq to a? j is 22 i is 0
scan_count: -1 count: 1
m eq to a? j is 22 i is 1
m eq to m? j is 21 i is 1
scan_count: 0 count: 2
a eq to a? j is 22 i is 2
scan_count: 1 count: 3
a eq to a很好，匹配…M是在下一次迭代中找到的，但是当你找到下一个"a"时，你会在巴拿马的末尾找到原来的"a"……
作为一个旁注，因为你每次都是从最后开始，它将是非常低效的O(n^2)给定一个足够大的字符串…
的解决方案:
$word = "amanaplana canalpan ama";
$j = strlen ($word)-1;
$pal = true;
for ($i = 0; $i < strlen($word)/2; ++$i, --$j) {
// skip spaces
while ($word[$i] === " ") {$i++;}
while ($word[$j] === " ") {$j--;}
echo "$word[$i] eq $word[$j]?'n";
if ($word[$i] !== $word[$j]) {
$pal = false;
break;
}
}
if ($pal) print "yes"; else print "no";
伪代码:
string phrase = "my phrase here"
int i = 0
int j = phrase.length - 1
while i < j:
if phrase[i] is not alphanumeric:
i++;
continue;
if phrase[j] is not alphanumeric:
j--;
continue;
if phrase[i] != phrase[j]
return false;
i++;
j--;
return true
我认为完全可以删除所有空格并完全忽略单词。将字符串分成两半(如果字符串长度为奇数，则大约为两半)，将任意一半的字符串倒过来，然后看看它们是否匹配。
$word = "amanaplana canalpan ama";
$sanitizedWord = preg_replace("''s+'", '', strtolower($word));
$halfway = strlen($sanitizedWord)/2;
$roundedDownMidPoint = floor($halfway);
$firstHalf = substr($sanitizedWord, 0, $roundedDownMidPoint);
$secondHalf = substr($sanitizedWord, is_float($halfway) ? $roundedDownMidPoint+1 : $halfway);
if ($firstHalf === strrev($secondHalf)) {
echo $sanitizedWord." is a palindrome";
}
用"Kayak"， "Racecar"， "Anna"， "A man A plan A canal Panama"answers" amanplana canalpan ama"进行测试，这些都被正确识别为回文
<?php
$a="amanaplana canalpan ama";
echo "String entered: " . $a;
$b= preg_replace('/'s+/', '', $a);
$org= strtolower($b);
$chk= strrev($org);
echo "<br/>";
if ($org==$chk)
{ echo "Palindrome"; }
else
{ echo "Not Palindrome"; }
?>