侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【双指针, 中心扩展】最长回文子串

GabrielxD
2022-06-05 / 0 评论 / 0 点赞 / 29 阅读 / 597 字 / 正在检测是否收录...

题目

5. 最长回文子串


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

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

解题

方法一:暴力(超时)

思路

暴力遍历,把所有字串找出来验证是否回文。

代码

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length(), maxSubLen = 0;
        String ans = "";
        for (int i = 0; i < len; i++) {
            for (int j = i + maxSubLen; j <= len; j++) {
                String subStr = s.substring(i, j);
                if (subStr.equals(new StringBuilder(subStr).reverse().toString())) {
                    maxSubLen = j - i;
                    ans = subStr;
                }
            }
        }
        return ans;
    }
}

方法二:双指针 中心扩展

思路

遍历字符串中每个字符,以字符作中心向两边扩展,扩展的规则为,左右边缘外的两个字符相等,每次扩展到最长时都会和前几次最长的回文子串长度作比较,取最长,最后返回最长的回文子串。

代码

class Solution {
    public int len, start = 0, maxSubLen = 1;

    public String longestPalindrome(String s) {
        len = s.length();
        for (int i = 0; i < len; i++) {
            extend(s, i, i);
            extend(s, i, i + 1);
        }

        return s.substring(start, start + maxSubLen);
    }

    public void extend(String s, int left, int right) {
        while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        int subLen = right - left - 1;
        if (subLen > maxSubLen) {
            start = left + 1;
            maxSubLen = subLen;
        }
    }
}

优化

在多次要取字符串中字符的情况下,把字符串转为字符数组,取数组中的字符更快,是一种空间换时间的方法。

class Solution {
    private char[] charArr;
    private int n;
    private int begin = 0, maxSubLen = 1;

    public String longestPalindrome(String s) {
        charArr = s.toCharArray();
        n = charArr.length;
        for (int i = 0; i < n; i++) {
            extend(i, i);
            extend(i, i + 1);
        }
        return s.substring(begin, begin + maxSubLen);
    }

    private void extend(int start, int end) {
        while (start >= 0 && end < n && charArr[start] == charArr[end]) {
            start--;
            end++;
        }
        int subLen = end - ++start;
        if (subLen > maxSubLen) {
            maxSubLen = subLen;
            begin = start;
        }
    }
}
class Solution {
    string s;
    int n;
    int max_sub_begin = 0, max_sub_len = 1;

    void extend(int left, int right) {
        while (left >= 0 && right < n && s[left] == s[right]) --left, ++right;
        int len = right - ++left;
        if (len > max_sub_len) {
            max_sub_len = len;
            max_sub_begin = left;
        }
    }

public:
    string longestPalindrome(string _s) {
        s = _s;
        n = s.size();
        for (int i = 0; i < n; ++i) {
            extend(i, i);
            extend(i, i + 1);
        }
        return s.substr(max_sub_begin, max_sub_len);
    }
};
0

评论区