最长回文子串 java语言

- 日理万妓 2024-03-30 17:34 11阅读 0赞

leetcode地址：[最长回文子串][Link 1]

描述：

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

**示例 1：**

**输入：**s = "babad"

**输出：**"bab"

**解释：**"aba" 同样是符合题意的答案。

**示例 2：**

**输入：**s = "cbbd"

**输出：**"bb"

**提示：**

*  1 <= s.length <= 1000

*  s 仅由数字和英文字母组成

public String longestPalindrome(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }
            int[] indexToArr = new int[2];
            int max = 0;
            char[] ss = s.toCharArray();
            for (int i = 0; i < ss.length; i++) {
                int high = i;
                //是偶数的时候
                while (high < ss.length - 1 && ss[i] == ss[high + 1]) {
                    high++;
                }
                int ans = high;
                //是奇数的时候
                while (i > 0 && high < ss.length - 1 && ss[i - 1] == ss[high + 1]) {
                    i--;
                    high++;
                }
                if (max < high - i) {
                    max = high - i;
                    indexToArr[0] = i;
                    indexToArr[1] = high;
                }
                i = ans;
            }
            return s.substring(indexToArr[0], indexToArr[1] + 1);
        }

题解：（**中心扩展法**）

最长回文子串存在两种情况：

①长度为偶数

s\[i\]==s\[i+1\] ; i++;

②长度为奇数

s\[l-1\]==s\[r+1\]; l--; r++;

首先判断不存在的情况

存在的情况下，定义一个长度为2的int数组用于存储子字符串的下标，定义两个变量也可以

那么for循环遍历整个字符串，使用变量ans记录i的位置，那么应该为ans=i；为什么代码中使用的是ans=high，是由于通过遍历的方式high指针已经前进了，并且i到high之间的字符串不可能超过之前找到子字符串的长度，因此，没必要一步步i++上来，每次比较max与当前长度的大小，得到最大的子字符串，并且记录下标位置到数组中，最后使用字符串的substring()函数得到最长的回文子字符串。

[Link 1]: https://leetcode.cn/problems/longest-palindromic-substring/description/