【必备算法】字符串（回文问题）：LeetCode题 647. 回文子串，5. 最长回文子串

傷城~ 2022-11-09 11:30 182阅读 0赞

## [647. 回文子串²][647.] ##

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

**示例 1:**

输入: "abc"
    输出: 3
    解释: 三个回文子串: "a", "b", "c".

**示例 2:**

输入: "aaa"
    输出: 6
    说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

### 解法一：枚举法（超时） ###

枚举出来所有子串，然后判断是否回文，回文就保存。

### 解法二：枚举中心 ###

*  思路：以每个元素都作为中心，向两边进行扩展
    
     *  向两边扩展的次数，就是以当期字符作为中心的回文串数
     *  注：这里要考虑中心是 单个元素 / 两个元素 这两种情况
 *  复杂度
    
     *  Time：O（n ^ 2)
     *  Space：O（1）

class Solution {
        
        public int countSubstrings(String s) {
        
            if (s == null || s.length() == 0) return 0;
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
        
                // 1.以当前字符为中心
                count += expand(s, i, i);
                // 2.以当前字符和相邻字符为中心
                count += expand(s, i, i+1);
            }
            return count;
        }
    
        private int expand(String s, int left, int right) {
        
            int count = 0;
            // 注：因为是向两边扩散，所以这里的条件是 left >= 0, right < len
            while (left >= 0 && right < s.length()) {
        
                if (s.charAt(left) != s.charAt(right)) return count;
                // 扩散一次就代表有一个以当前为中心的回文串
                count++;
                left--; right++;
            }
            return count;
        }
    
    }

## [5. 最长回文子串²][5.] ##

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

**示例 1：**

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

**示例 2：**

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

### 解法一：枚举法（超时） ###

枚举出来所有子串，然后判断是否回文，然后记录长度求最长。

### 解法二：枚举中心 ###

*  思路：计算以每个字符(i)为中心的回文串长度(len) --> 再用start标记起始位置即可（start=i-(len-1)/2)
 *  复杂度
    
     *  Time：O（n²）
     *  Space：O（1）

class Solution {
        
        
        public String longestPalindrome(String s) {
        
            int start = 0, maxLen = 0;
            for (int i = 0; i < s.length(); i++) {
        
                // 中心奇数 aba
                int len1 = countLen(s, i, i);
                // 中心偶数 abba
                int len2 = countLen(s, i, i+1);
                int len = Math.max(len1, len2);
                // 更新start，-1是因为len包含了当前字符
                if (len > maxLen) {
        
                    start = i - (len - 1) / 2;
                    maxLen = len;
                }
            }
            return s.substring(start, start + maxLen);
        }
    
        int countLen(String s, int left, int right) {
        
            // 从中心向两边扩散
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        
                left--; right++;
            }
            return right - left - 1;
        }
    }

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