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

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 提交结果

参考资料

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