萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 判斷回文字串演算法實現與優化指南

回文判斷:經典演算法面試題

回文(Palindrome)指正讀反讀相同的字串。本文提供多種 PHP 實現方案,從基礎循環到內建函數優化,分析時間/空間複雜度與適用場景。

方案一:雙指標循環法(原始代碼優化版)

<?php
function isPalindromeLoop(string $str): bool {
    $len = strlen($str);
    // 只需比較前半段
    for ($i = 0; $i < $len / 2; $i++) {
        if ($str[$i] !== $str[$len - 1 - $i]) {
            return false;
        }
    }
    return true;
}

// 測試
var_dump(isPalindromeLoop("12321"));  // true
var_dump(isPalindromeLoop("hello"));  // false
var_dump(isPalindromeLoop("madam"));  // true
?>

複雜度:時間 O(n/2) = O(n),空間 O(1)

方案二:內建函數一行解決(推薦生產環境)

<?php
function isPalindromeBuiltin(string $str): bool {
    return $str === strrev($str);
}

var_dump(isPalindromeBuiltin("racecar"));  // true
?>

優點:C 層實現極快、代碼極簡、可讀性最佳
注意:strrev() 不支援多位元組字元(UTF-8 中文會亂碼)

方案三:多位元組安全版(支援中文/Emoji)

<?php
function isPalindromeMb(string $str): bool {
    // 將字串轉為字元陣列(支援 UTF-8)
    $chars = preg_split('//u', $str, -1, PREG_SPLIT_NO_EMPTY);
    $len = count($chars);
    
    for ($i = 0; $i < $len / 2; $i++) {
        if ($chars[$i] !== $chars[$len - 1 - $i]) {
            return false;
        }
    }
    return true;
}

var_dump(isPalindromeMb("上海自來水來自海上"));  // true
var_dump(isPalindromeMb("你好世界"));          // false
var_dump(isPalindromeMb("👨‍👩‍👧‍👦"));        // true (家庭 emoji 為單一字素簇)
?>

方案四:遞歸實現(教學用,生產慎用)

<?php
function isPalindromeRecursive(string $str): bool {
    $len = strlen($str);
    if ($len <= 1) return true;
    if ($str[0] !== $str[$len - 1]) return false;
    return isPalindromeRecursive(substr($str, 1, -1));
}

// 注意:深度遞歸會耗盡棧空間,長字串會報錯
?>

方案五:正則表達式(學術探討)

<?php
// 僅適用極短字串,效能極差,不推薦生產使用
function isPalindromeRegex(string $str): bool {
    $len = strlen($str);
    $pattern = '^';
    for ($i = 0; $i < $len / 2; $i++) {
        $pattern .= '(.)';
    }
    $pattern .= ($len % 2 ? '.' : '');
    for ($i = (int)($len / 2) - 1; $i >= 0; $i--) {
        $pattern .= '\\' . ($i + 1);
    }
    $pattern .= '$';
    
    return (bool)preg_match("/$pattern/", $str);
}
?>

效能基準測試

<?php
function benchmark(callable $fn, string $input, int $iterations = 100000): float {
    $start = hrtime(true);
    for ($i = 0; $i < $iterations; $i++) {
        $fn($input);
    }
    return (hrtime(true) - $start) / 1e9;
}

$testStr = str_repeat("ab", 500) . "x" . str_repeat("ba", 500); // 2001 字元非回文

echo "Loop: " . benchmark('isPalindromeLoop', $testStr) . "s<br>";
echo "Builtin: " . benchmark('isPalindromeBuiltin', $testStr) . "s<br>";
echo "Mb: " . benchmark('isPalindromeMb', $testStr) . "s<br>";

// 典型結果(相對):
// Builtin ~ 0.02s (最快,C層)
// Loop ~ 0.08s
// Mb ~ 0.45s (preg_split 開銷大)
?>

擴展應用:最長回文子串(Manacher 算法 PHP 實現)

<?php
function longestPalindrome(string $s): string {
    if (strlen($s) < 2) return $s;
    
    // 預處理:插入特殊字元統一奇偶長度
    $t = '#' . implode('#', str_split($s)) . '#';
    $n = strlen($t);
    $p = array_fill(0, $n, 0);
    $center = $right = 0;
    $maxLen = $maxCenter = 0;
    
    for ($i = 0; $i < $n; $i++) {
        $mirror = 2 * $center - $i;
        if ($i < $right) {
            $p[$i] = min($right - $i, $p[$mirror]);
        }
        
        // 嘗試擴展
        while ($i + $p[$i] + 1 < $n && $i - $p[$i] - 1 >= 0 && $t[$i + $p[$i] + 1] === $t[$i - $p[$i] - 1]) {
            $p[$i]++;
        }
        
        // 更新最右邊界
        if ($i + $p[$i] > $right) {
            $center = $i;
            $right = $i + $p[$i];
        }
        
        // 記錄最長
        if ($p[$i] > $maxLen) {
            $maxLen = $p[$i];
            $maxCenter = $i;
        }
    }
    
    $start = ($maxCenter - $maxLen) / 2;
    return substr($s, $start, $maxLen);
}

echo longestPalindrome("babad");  // "bab" 或 "aba"
echo longestPalindrome("cbbd");   // "bb"
?>

實際應用場景

場景推薦方案備註
純 ASCII 字串驗證strrev() 比較最快、最簡潔
UTF-8 多語言支援preg_split //u + 循環正確處理字素簇
超長字串 (MB 級)流式處理 + 雙指標避免載入整個字串
數字回文 (不轉字串)數學反轉法整數運算,無字串開銷
找最長回文子串Manacher O(n)線性時間最優

數字回文不轉字串

<?php
function isNumericPalindrome(int $x): bool {
    if ($x < 0) return false;  // 負數非回文
    if ($x % 10 === 0 && $x !== 0) return false;  // 尾數為0的非零數
    
    $reversed = 0;
    while ($x > $reversed) {
        $reversed = $reversed * 10 + $x % 10;
        $x = (int)($x / 10);
    }
    // 奇數長度:中間位數在 $reversed/10
    return $x === $reversed || $x === (int)($reversed / 10);
}

var_dump(isNumericPalindrome(12321));  // true
var_dump(isNumericPalindrome(123321)); // true
var_dump(isNumericPalindrome(-121));   // false
?>

總結

  • ASCII 字串:$str === strrev($str) 一行解決,效能最優
  • UTF-8 字串:preg_split('//u') 轉字元陣列再雙指標比較
  • 數字回文:數學反轉法避免字串轉換開銷
  • 最長回文子串:Manacher 算法 O(n) 線性時間
  • 避免遞歸:PHP 無尾呼叫優化,長輸入會棧溢出
copyright © 萬盛學電腦網 all rights reserved