leetcode|中等:5. 最长回文子串

jupiter
2022-03-23 / 0 评论 / 519 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月23日,已超过758天没有更新,若内容或图片失效,请留言反馈。

1.题目

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

示例 1:

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

示例 2:

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

提示:

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

2. 题解

2.1 思路分析

思路1:暴力求解
    从每个字符开始向右延伸探索可能构成的最长回文子串并记录最长子串的开始位置和长度

2.2 代码实现

public class Solution {
    //判断子串是否构成回文
    public boolean isPalindrome(char[] sChars,int indexStart,int indexEnd){
        int len = indexEnd-indexStart;
        if(len==1)return true;

        for (int i = 0; i < len/2; i++) {
            if(sChars[indexStart+i]!=sChars[indexEnd-1-i]){
                return false;
            }
        }

        return true;
    }

    public String longestPalindrome(String s) {
        char[] sChars = s.toCharArray(); //转为字符数组
        int sLen = s.length(); // 字符串长度
        int indexStart = 0; //记录最长子串的开始位置
        int maxLen = 1; //记录最大子串长度

        for (int i = 0; i < sLen-maxLen; i++) { // 子串开始下标
            for (int j = maxLen; j <= sLen-i; j++) { // 子串长度
                if(isPalindrome(sChars,i,i+j)){
                    indexStart = i;
                    maxLen = j;
                }
            }
        }

        return s.substring(indexStart,indexStart+maxLen);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String in = "babad";
        String res = solution.longestPalindrome(in);
        System.out.println(res);
    }
}

2.3 提交结果

提交结果执行用时内存消耗语言提交时间备注
通过265 ms41.2 MBJava2022/03/23 17:11添加备注

参考资料

  1. https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
0

评论 (0)

打卡
取消