欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

5.最长的回文子串

最编程 2024-06-01 09:48:23
...

5.最长回文子串

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

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

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = huiWen(s, i, i);
            String s2 = huiWen(s, i, i + 1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    public String huiWen(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            // 两边扩
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

}

思路:从头遍历字符串

  1. 以0位置为起点,向两边扩,找到最大回文字符串;

    • 再以0和1(0 + 1)位置为起点,向两边扩,找到最大回文数;

    • 记录最长的最大回文数

  2. 以1位置为起点,向两边扩,找到最大回文字符串;

    • 再以1和2(1 + 1)位置为起点,向两边扩,找到最大回文数;

    • 记录最长的最大回文数

  3. 一次类推.......

推荐阅读