1

我正在（为了好玩）编写一个可以识别回文的脚本。到目前为止，我在“Kayak”、“Racecar”、“Anna”、“A man a plan a canal Panama”方面取得了成功：但后一个短语的变体，如“amanaplana 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";
}


?>

我很感激有关以下方面的回应：

  • 我遇到的错误的识别。
  • 关于如何改进代码的建议（如果我可以在不诉诸 $count 或 $scan_count 的情况下使事情正常进行，在我看来，这似乎是相对业余的）。

提前致谢。

4

5 回答 5

3

目前，您正在逐字逐句地进行测试，如果回文中的单词不均匀，这肯定会导致错误。

在 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.';
于 2011-07-17T06:28:31.573 回答
2

这里发生了一些事情...

首先，我不确定您是否知道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){

给定“amanaplanacanacanalpanama”，看看你在做什么：

比较，一步一步（顺便说一句，你在 $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";
于 2011-07-17T13:00:04.510 回答
1

伪代码：

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
于 2011-07-17T06:35:53.793 回答
0

我认为可以删除所有空格并完全忽略单词。只需分成两部分（如果字符串长度是奇数，则大约是这样），反转任何一半，然后查看它们是否匹配。

$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”和“amanaplana canalpan ama”进行测试，这些都被正确识别为回文。

于 2011-07-17T06:51:20.363 回答
0 
<?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"; }
?>
于 2014-03-17T08:19:20.627 回答