回文(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 中文會亂碼)
<?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 開銷大)
?>
<?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
?>
$str === strrev($str) 一行解決,效能最優preg_split('//u') 轉字元陣列再雙指標比較