Leetcode-005-最长回文子串

Leecode-005-Longest Palindromic Substring

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

方法一 ：中心扩散法

中心扩散法的思路是：

• 遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散到多远。

• 枚举“中心位置”时间复杂度为 O(N)，同时从“中心位置”扩散得到“回文子串”的时间复杂度为 O(N)，因此时间复杂度可以降到O(N^2)。

• 在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

  • 奇数回文串的中心是一个具体的字符。例如：回文串 "aba" 的中心是字符 "b"；
  • 偶数回文串的中心是两个字符的空隙，例如：回文串 "abba" 的中心是两个 "b" 中间的那个“空隙”。

那么接下来问题的就是回文子串的中心在哪里？

• 我们可以设计一个方法，兼容以上两种情况：

1、如果传入重合的索引编码，进行中心扩散，此时得到的回文子串的长度是奇数；

2、如果传入相邻的索引编码，进行中心扩散，此时得到的回文子串的长度是偶数。

具体编码细节在以下的代码的注释中体现。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1){
            return "";
        }

        // 初始化最大回文子串的起点和终点
        int start = 0;
        int end   = 0;

        // 遍历每个位置，当做中心位
        for (int i = 0; i < s.length(); i++) {
            // 分别拿到奇数偶数的回文子串长度
            int len_odd = expandCenter(s,i,i);
            int len_even = expandCenter(s,i,i + 1);
            // 对比最大的长度
            int len = Math.max(len_odd,len_even);
            // 计算对应最大回文子串的起点和终点
            if (len > end - start){
                start = i - (len - 1)/2;
                end = i + len/2;
            }
        }
        // 注意：这里的end + 1是因为 java自带的左闭右开的原因
        return s.substring(start,end + 1);
    }


    /**
     *
     * @param s             输入的字符串
     * @param left          起始的左边界
     * @param right         起始的右边界
     * @return              回文串的长度
     */
    private int expandCenter(String s,int left,int right){
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        // 跳出循环的时候恰好满足 s.charAt(left) ！= s.charAt(right)
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        // 回文串的长度是right-left+1-2 = right - left - 1
        return right - left - 1;
    }
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。

方法二： 动态规划

从回文串的定义展开讨论：

• 如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
• 如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
  • 如果里面的子串是回文，整体就是回文串；
  • 如果里面的子串不是回文串，整体就不是回文串。

1. 定义状态

dp[i][j] 表示子串s[i…j] 是否是回文串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。

2. 状态转移方程

在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

说明：

• 「动态规划」事实上是在填一张二维表格，由于构成子串，因此 i 和 j 的关系是 i <= j ，因此，只需要填这张表格对角线以上的部分。

• 看到 dp[i + 1][j - 1] 就得考虑边界情况。

边界条件：

边界条件是：
表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，
即 j - 1 - (i + 1) + 1 < 2 ，
整理得 j - i < 3。

这个结论很显然：

• j - i < 3 等价于 j - i + 1 < 4
  - 即当子串的长度等于2或者等于3的时候，其实只要判断一下头尾两个字符是否相等就可以直接下结论了。
    - 如果子串 `s[i + 1..j - 1]` 只有 1 个字符，即去掉两头，剩下中间部分只有 11 个字符，显然是回文；
    - 如果子串 `s[i + 1..j - 1]` 为空串，那么子串 `s[i, j]` 一定是回文子串。
  
  - 因此在 ， s[i] == s[j]的前提下，直接可以下结论，`dp[i][j] = true`，否则才执行状态转移。
  
  
  
  3. **初始化**
  
  初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true 。
  
  事实上，初始化的部分都可以省去。因为只有一个字符的时候一定是回文，dp[i][i] 根本不会被其它状态值所参考。
  
  
  
  4. **考虑输出**
  
  只要一得到`dp[i][j] = true`，就记录子串的长度和起始位置，没有必要进行截取
  
  记录此时回文串的起始位置和回文长度即可
  
  
  
  ```java
  class Solution {
      public String longestPalindrome(String s) {
          int len = s.length();
          // 特判
          if (len < 2){
              return s;
          }
  
          int maxLen = 1;
          int begin  = 0;
  
          // 1. 状态定义
          // dp[i][j] 表示s[i...j] 是否是回文串
  
  
          // 2. 初始化
          boolean[][] dp = new boolean[len][len];
          for (int i = 0; i < len; i++) {
              dp[i][i] = true;
          }
  
          char[] chars = s.toCharArray();
          // 3. 状态转移
          // 注意：先填左下角
          // 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算
          for (int j = 1;j < len;j++){
              for (int i = 0; i < j; i++) {
                  // 头尾字符不相等，不是回文串
                  if (chars[i] != chars[j]){
                      dp[i][j] = false;
                  }else {
                      // 相等的情况下
                      // 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
                      if (j - i < 3){
                          dp[i][j] = true;
                      }else {
                          // 状态转移
                          dp[i][j] = dp[i + 1][j - 1];
                      }
                  }
  
                  // 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
                  // 此时更新记录回文长度和起始位置
                  if (dp[i][j] && j - i + 1 > maxLen){
                      maxLen = j - i + 1;
                      begin = i;
                  }
              }
          }
          // 4. 返回值
          return s.substring(begin,begin + maxLen);
      }
  }
  

打赏