5. 最长回文子串

题意

解题思路:

• 动态规划三部曲：
• dp状态定义：dp[i][j] 字符串从i到j是否是回文串，如果是，当前长度是j - i + 1
• dp初始化：$res = $s[0];
• dp状态转移方程： s[i] == s[j] dp[i][j] = dp[i+1][j-1]//回文串的子串也是回文串：babab

PHP 代码实现

class Solution {
    public $res = '';
    public $max = 0;
    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        if (strlen($s) <= 1) return $s;
        for ($i = 0; $i < strlen($s); $i++) {
            $this->extendByCenter($s, $i, $i);//aba
            $this->extendByCenter($s, $i, $i + 1);//abba
        }
        return $this->res;
    }
    //暴力法
    function longestPalindrome1($s) {
        $len = strlen($s);
        if ($len < 2) return $s;
        $maxLen = 1;
        $res = substr($s, 0, 1);
        for ($i = 0; $i < $len - 1; $i++) {
            for ($j = $i + 1; $j < $len; $j++) {
                if ($j - $i + 1 > $maxLen && $this->valid($s, $i, $j)) {
                    $maxLen = $j - $i + 1;
                    $res = substr($s, $i, $j - $i + 1);
                }
            }
        }
        return $res;
    }
        // 验证子串 s[left, right] 是否为回文串
    function valid($s, $left, $right) {
        while ($left < $right) {
            if ($s[$left] != $s[$right]) return false;
            $left++;
            $right--;
        }
        return true;
    }
    //中心扩散法
    function extendByCenter($s, $left, $right) {
        while ($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
            if ($right - $left + 1 > $this->max) {
                $this->max = $right - $left + 1;
                $this->res = substr($s, $left, $right - $left + 1);
            }
            $left--;
            $right++;
        }
    }
    //动态规划：保存子问题的解来求解原问题的解
    function dplongestPalindrome($s) {
        if (strlen($s) <= 1) return $s;
        $res = $s[0];//1个字符也是回文串
        $max = 0;
        //2个字符的情况
        if ($s[0] == $s[1]) {
            $res = substr($s, 0, 2);
        }
        for ($j = 2; $j < strlen($s); $j++) {
            $dp[$j][$j] = true;//1个字符肯定是回文串
            for ($i = 0; $i < $j; $i++) {
                // aab3baa : $j - $i <= 2, 中间隔一个字母的情况也是回文串：b3b
                $dp[$i][$j] = $s[$i] == $s[$j] && ($j - $i <= 2 || $dp[$i + 1][$j - 1]);
                if ($dp[$i][$j] && $max < $j - $i + 1) {
                    $max = $j - $i + 1;
                    $res = substr($s, $i, $j - $i + 1);
                }
            }
        }
        return $res;
    }
}

GO 代码实现

func longestPalindrome(s string) string {
    if s == "" {
        return ""
    }
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        left1, right1 := expandCenter(s, i, i)
        left2, right2 := expandCenter(s, i, i+1)
        step := end - start
        if right1 - left1 > step {
          start, end =  left1, right1 
        }
        if right2 - left2 > step {
          start, end =  left2, right2 
        }
    }
    return s[start: end + 1]
}
func expandCenter(s string, left, right int) (int, int) {
    for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {}
    return left + 1, right - 1
}