4. 最长回文子串

<?php
class Solution {
    public $res = "";
    public $max = 0;
    // 中心扩散
    public function longestPalindrome($s) {
        $this->init();
        if (strlen($s) <= 1) return $s;
        for ($i = 0; $i < strlen($s); $i++) {
            $this->diffusion($s, $i, $i);
            $this->diffusion($s, $i, $i + 1);
        }
        return $this->res;
    }
    private function diffusion($s, $left, $right) {
        while($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
            $newLen = $right - $left + 1;
            if ($newLen > $this->max) {
                $this->max = $newLen;
                $this->res = substr($s, $left, $newLen);
            }
            $left--;
            $right++;
        }
    }
    // 动态规划
    public function longestPalindrome2($s) {
        $this->init();
        if (strlen($s) <= 1) return $s;
        $this->res = $s[0];
        if ($s[0] == $s[1]) {
            $this->res = substr($s, 0, 1);
        }
        for ($j = 2; $j < strlen($s); $j++) {
            $dp[$j][$j] = true;
            for($i = 0; $i < $j; $i++) {
                $dp[$i][$j] = ($s[$i] == $s[$j]) && (($j - $i <= 2) || $dp[$i + 1][$j - 1]);
                if ($dp[$i][$j] && $this->max < $j - $i + 1) {
                    $this->max = $j - $i + 1;
                    $this->res = substr($s, $i, $j - $i + 1);
                }
            }
        }
        return $this->res;
    }
    private function init() {
        $this->res = '';
        $this->max = 0;
    }
}
$str = 'abbasabbbb';
$cls = new Solution();
$ret = $cls->longestPalindrome($str);
print_r($ret);
echo "\n";
$ret2 = $cls->longestPalindrome2($str);
print_r($ret2);