JAVA 牛牛

5. 最长回文串

  • May 01, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 中心扩展算法
  • 思路： 中心扩展算法
  • 类似题型:

题目 5. 最长回文子串

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

示例

示例 1：

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

示例 2：

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

方法一 中心扩展算法

解题思路

  1. 首先，要明白 expandAroundCenter 函数作用是以一个中心向两侧扩展找到这个中心最长回文串的长度，参数 left 和 right 就是为了指定中心。
  2. 其次，中心可能是一个或两个字符。如：对于字符串“abcda”，“c”是中心；对于字符串“adccda”，“cc”是中心。
  3. 那么，expandAroundCenter(s, i, i) 就是在找以 i（一个字符）为中心的最长回文串的长度；expandAroundCenter(s, i, i + 1) 是在找以 i 和i+1（两个字符）为中心的最长回文串的长度。
  4. 将得到的两个长度和缓存的最长回文串长度相比较。若新得到的长度较长，表达式：$start = i - (len - 1) / 2$;$end = i + len / 2$; 就得出了新的最长回文串的开始和结束位置。
  5. 最后，for循环遍历了一遍，以一个字符为中心总共找了 n 次，以两个字符为中心总共找了 n-1 次，所以说“总共有2n−1 个这样的中心”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i); // 一个中心的情况 aba
        int len2 = expandAroundCenter(s, i, i + 1); // 两个中心的情况 abba
        int len = Math.max(len1, len2);
        if (len > end - start) { // 每次循环 判断最长的回文串首尾
            start = i - (len - 1) / 2; // 当一个中心的情况 start = i - len/2 当两个中心的情况 i 右边做了 i+1 操作 所以 len -1
            end = i + len / 2; // 这个还好理解
        }
    }
    return s.substring(start, end + 1);
}

// 中心扩展算法
private int expandAroundCenter(String s, int left, int right) {
  while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
          left--;
          right++;
      }
      return right - left - 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def longestPalindrome(self,s: str) -> str:
        start , end = 0 , 0

        for i in range(len(s)-1):
            lenOne = self.expandAroundCenter(s,i,i) # 一个中心的情况 aba
            lenTwo = self.expandAroundCenter(s,i,i+1) # 两个中心的情况 abba
            lenMax = max(lenOne,lenTwo)
            if lenMax > end - start: # 每次循环 判断最长的回文串首尾
                start = i - (lenMax-1)//2 # // 当一个中心的情况 start = i - len/2 当两个中心的情况 i 右边做了 i+1 操作 所以 len -1
                end = i + lenMax//2 # 这个还好理解

        return s[start:end+1]
    # 中心扩展算法
    def expandAroundCenter(self,s:str ,left:int,right:int) ->int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left = left -1
            right = right +1
        return right - left -1


if __name__ == "__main__":
    st = 'abcba'
    solution = Solution() # 有括号和没有括号的区别
    res = solution.longestPalindrome(st)
    print(res)
Search