leetcode——最长回文子串——百日算法成就第五天5%

leetcode——最长回文子串——百日算法成就第五天5%

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring

1. 题目描述

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

2. 示例

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

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

3. 方法一：暴力方法

给出一个字符串，我们可以把他转为字符数组，用双重循坏外层表示回文子串的起始下标，内层循环表示回文子串的终止下标，进行判断该区间内的子串是否是回文子串。这种方法提交在LeetCode上会提示超出时间限制

代码：

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class LongestPalindrome {
    public static String longestPalindrome(String s) {
        if (s.length()<2){
            return s;
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length()-1; i++) {
            for (int j = i+1; j < s.length(); j++) {
                if ((j-i)>(end-start) && palindrome(s,i,j)){
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start,end+1);
    }
    public static boolean palindrome(String s, int i, int j){
        char[] chars = s.toCharArray();
        int start = i;
        int end = j;
        for (int k = start; k <= end; k++) {
            if (chars[i]==chars[j]){
                i++;
                j--;
            }else {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        String str = "201023312000000";
        String s = longestPalindrome(str);
        System.out.println(s);
    }
}

提交截图：

4. 方法二 ：中心拓展法

从回文子串的中心往两边比较

代码：

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 中心拓展法
 */
public class LongestPalindrome1 {
    public static String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int start = 0;
        int max = 0;
        int maxLength = 0;
        int l1 = 0;
        int l2 = 0;
        for (int i = 0; i < s.length()-1; i++) {
            l1 = palindrome(s, i, i);
            l2 = palindrome(s, i, i + 1);
            maxLength = l1 > l2 ? l1 : l2;
            if (maxLength > max) {
                max = maxLength;
                start = i;
            }
        }
        return s.substring(start- (max-1)/2 , start + max/2+1);
    }

    public static int palindrome(String s, int i, int j) {
        char[] chars = s.toCharArray();
        int l = 1;
        for (; ; ) {
            if (chars[i] == chars[j]) {
                l = j - i +1;
                i--;
                j++;
            }else {
                break;
            }
            if (i < 0 || j >= s.length()){
                break;
            }
        }
        return l;
    }
    public static void main(String[] args) {
        String str = "123456";
        String s = longestPalindrome(str);
        System.out.println(s);
    }
}

提交截图：