題目要求
給定一個字串 s，找到 s 中最長的回文子串，你可以假設 s 的最大長度為 1000，
（具體要求請看5. 最長回文子串）
解題思路
參考了各路大神的解題思路，就這種我感覺比較容易理解一點，所以就采用了中心擴展演算法，等我再好好看看馬拉車演算法再和大家分享吧，
首先要了解回文的特點，它是關于中心對稱的，這樣的對稱分為兩種情況，一種的長度為奇數的字串，一種是長度為偶數的字串，根據這個特點，就可以分別比較中心兩側對應的字符，通過判斷兩側對應字符是否相同來得出當前判斷的子串是否為回文，代碼如下：
代碼
class Solution {
protected $len = 0; // 字串長度
protected $start = 0; // 起始位置
protected $length = 0; // 截取長度
/**
* @param String $s
* @return String
*/
public function longestPalindrome($s) {
$this->len = strlen($s);
for ($i = 0; $i < $this->len; $i++) {
// 如果起始位置 + 截取長度 = 字串長度，就不需要繼續回圈下去，因為可以確定當前長度是最長的
if ($this->start + $this->length >= $this->len) break;
$this->expandAroundCenter($s, $i, $i); // 情況 1： aba
$this->expandAroundCenter($s, $i, $i + 1); // 情況 2： bb
}
// 使用 substr 函式，截取相應的字串
return substr($s, $this->start, $this->length);
}
/**
* @param String $str
* @param Integer $left
* @param Integer $right
*/
protected function expandAroundCenter($str, $left, $right) {
// 這里判斷左右兩邊對應字符是否相等，如果相等，left-1，right+1，繼續比較
while ($left >= 0 && $right < $this->len && $str[$left] === $str[$right]) {
$left--;
$right++;
}
// 當上面回圈結束，也就是找到了一個回文子串
// temp 是子串的長度
$temp = $right - $left - 1;
// 與 length 比較，看當前找到的子串是否是較長的那個，
// 如果是，就給 start 和 length 賦值
if ($this->length < $temp) {
$this->start = $left + 1;
$this->length = $temp;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/49459.html
標籤：PHP
上一篇：Linux 上安裝 PHP 擴展