【腾讯精选练习 50 题】08—最长回文子串【中等】

系统管理员 2022-11-01 10:57 296阅读 0赞

### 文章目录 ###

*   *  题目链接
     *  题目简介
     *  题目解析
     *  题目代码
     *   *  动态规划代码
         *  中心扩散代码

## 题目链接 ##

[5. 最长回文子串【中等】][5.]

## 题目简介 ##

给你一个字符串 s，找到 s 中最长的回文子串。  
**示例 1：**

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

**示例 2：**

输入：s = "cbbd"
    输出："bb"

**示例 3：**

输入：s = "a"
    输出："a"

**示例 4：**

输入：s = "ac"
    输出："a"

## 题目解析 ##

1.  该题目有两种做法：动态规划和中间扩散
2.  对于动态规划来说：
    
     *  我们使用 `vis[i][j]` 来标记 `i~j` 之间的字符串是否为回文串
     *  对于如何判断我们 `i~j` 之间是否为回文串，我们去查看其 `vis[i + 1][j-1]` 是否为回文字符串
     *  我们需要计算 `j - 1 - i - 1 + 1 < 2 化简为 j - i < 3`
     *  最后不断更新 **`manLen`** 和 **`begin`** 的值即可
3.  对于中间扩散来说：
    
     *  我们从中间来判断该字符串是否为回文串，依次进行扩散
     *  在扩散的时候，需要考虑更新当前 `begin` 和 `end` 的值
     *  分别考虑偶数和奇数的情况
     *  最后取最大值返回即可

## 题目代码 ##

### 动态规划代码 ###

public String longestPalindrome(String s) {
        
            if (s.length() < 2) {
        
                return s;
            }
    
            boolean[][] vis = new boolean[s.length()][s.length()];
    
    
            int begin = 0;
            int maxLen = 1;
            for (int i = 0; i < s.length(); i++) {
        
                vis[i][i] = true;
            }
    
            for (int j = 0; j < s.length(); j++) {
        
                for (int i = 0; i < j; i++) {
        
                    if (s.charAt(i) != s.charAt(j)) {
        
                        vis[i][j] = false;
                    } else {
        
                        if (j - i < 3) {
        
                            vis[i][j] = true;
                        } else {
        
                            vis[i][j] = vis[i + 1][j - 1];
                        }
                    }
    
                    if (vis[i][j] && j - i + 1> maxLen) {
        
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
    
            return s.substring(begin, maxLen);
        }

### 中心扩散代码 ###

public String longestPalindrome1(String s) {
        
            int len = s.length();
            if (len < 2) {
        
                return s;
            }
    
            int begin = 0;
            int end = 0;
    
    
            for (int i = 0; i < len; i++) {
        
                int left = judgmentString(s, i, i);
                int right = judgmentString(s, i, i + 1);
                int maxLen = Math.max(left, right);
    
                if (end - begin < maxLen) {
        
                    begin = i - (maxLen - 1) / 2;
                    end = i + maxLen / 2;
                }
    
            }
    
            return s.substring(begin, end + 1);
        }
    
        public int judgmentString(String s, int left, int right) {
        
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        
                left--;
                right++;
            }
            return right - 1 - left;
        }

[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/