5. 最长回文子串

  |   0 评论   |   0 浏览

来源力扣(LeetCode)
难度:中等

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

示例 1

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

示例 2

1输入: "cbbd"
2输出: "bb"

题解
方法一:暴力算法

 1class Solution {
 2    public String longestPalindrome(String s) {
 3        int len = s.length();
 4        if (len < 2) {
 5            return s;
 6        }
 7        
 8        // 最长回文字符串长度
 9        int maxLen = 1;
10        // 回文字符串起始索引
11        int begin = 0;
12        // 将字符串转为数组
13        char[] chars = s.toCharArray();
14
15        // 列举所有长度大于 1 的子串
16        for (int i = 0; i < s.length(); i++) {
17            for (int j = i + 1; j < s.length(); j++) {
18                if (j - i + 1 > maxLen && isPalindromic(chars, i, j)) {
19                    maxLen = j - i + 1;
20                    begin = i;
21                }
22            }
23        }
24
25        return s.substring(begin, begin + maxLen);
26    }
27
28    /**
29     * 判断 charArray[left,right] 之间的字符是否是回文
30     */
31    private boolean isPalindromic(char[] charArray, int left, int right) {
32        while (left < right) {
33            if (charArray[left] != charArray[right]) {
34                return false;
35            }
36            left++;
37            right--;
38        }
39        return true;
40    }
41}

方法二:中心扩展法

 1/**
 2 * 字符串中每个字符或者相邻的两个相同字符都可能是回文字符串的中心。
 3 * 因此,我们可以从每个字符(或相邻字符对)开始向外扩展,每次向左右扩展一个字符,如果这两个字符相同,则继续扩展。
 4 * 直到扩展的两个字符不同或者超过了边界,我们就找到了以这个字符(或字符对)为中心最长的回文字符串。
 5 * 比较每次找的的回文字符串,找出最长的那个。
 6 */
 7class Solution {
 8    public String longestPalindrome(String s) {
 9        // 回文字符串起始索引
10        int begin = 0;
11        int end = 0;
12        // 将字符串转为数组
13        char[] chars = s.toCharArray();
14
15        for (int i = 0; i < s.length(); i++) {
16            //回文中心是一个字符
17            int len1 = expandAroundCenter(chars, i, i);
18            // 回文中心是两个字符
19            int len2 = expandAroundCenter(chars, i , i+1);
20            int len = Math.max(len1, len2);
21
22            if (len > end - begin + 1) {
23                begin = i - (len-1)/2;
24                end = i + len/2;
25            }
26        }
27
28        return s.length() == 0 ? "" : s.substring(begin, end + 1);
29    }
30
31    /**
32     *
33     * @param chars 字符数组
34     * @param left
35     * @param right
36     * @return 回文字符串最大长度
37     */
38    private int expandAroundCenter(char[] chars, int left, int right) {
39        int lt = left;
40        int rt = right;
41        while (lt >= 0 && rt < chars.length && chars[lt] == chars[rt]) {
42            lt--;
43            rt++;
44        }
45        return rt - lt - 1;
46    }
47}