leetcode之每日一题

leetcode 5

最长回文子串

Posted by Static on May 21, 2020

题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

分析

1. 暴力

时间负责度:O(n^3) 第一层:从左侧开始，寻找最长的第二层:从左边开始遍历，匹配所有回文子串，为了第一步寻找最长回文子串第三层:从右边开始遍历，为了第二步匹配

代码实现

public enum Q5 {
    instance;

    // TODO: 2020/3/22 时间负责度较高
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        if (length == 0 || length == 1) {
            return s;
        }
        int max = 0, start = 0, end = 0;

        for (int i = 0; i < length; i++) {
            int j = length - 1;
            for (; j > i; ) {
                int count = 0;
                for (int a = i, b = j; b >= a; a++, b--) {
                    if (chars[a] == chars[b]) {
                        count++;
                    } else {
                        count = 0;
                        break;
                    }
                }

                // 寻找最长回文子串
                if (count != 0 && (count >= max) && (end - start < j - i)) {
                    max = count;
                    start = i;
                    end = j;
                }
                j--;
            }
        }
        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        // assert aa
        System.out.println(Q5.instance.longestPalindrome("aacdefcaa"));
    }
}