Skip to content

5. Longest Palindromic Substring

难度: Medium

刷题内容

原题连接

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

内容描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.


Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:

Input: "cbbd"
Output: "bb"

解题方案

思路 1 **- 时间复杂度: O(n^2)*- 空间复杂度: O(n^2)***

使用动态规划的思路,用一个二维数组cache[i][j]记录i到j是否为回文串, beats 54.36%

class Solution {
    // 采用动态规划
    // 如果 i == j ,则只有一个字母 肯定是回文串
    // 如果 char[i] == char[j] && j == i + 1 , 两个字母相等 肯定是回文串
    // 如果 char[i] == char[j] && j > i + 1 && cache[i+1][j-1]为true,则肯定是回文串
    public String longestPalindrome(String s) {
        if(s == null || s.length() <2){
            return s;
        }
        boolean[][] cache = new boolean[s.length()][s.length()]; // 记录 i ~ j 是否是回文串
        char[] chars = s.toCharArray();
        int len = s.length();
        int start = 0;
        int end = 0;
        // 采用至底向上的动态规划,也可以采用递归方式
        for(int i = len - 1; i >= 0; i --){
            for(int j = i; j < len; j ++){
                if(i == j){
                    cache[i][j] = true;    
                }else if(j == i + 1 && chars[i] == chars[j]){
                    cache[i][j] = true;
                    if(end - start + 1 < 2){
                        end = j;
                        start = i;
                    }
                }else if(chars[i] == chars[j] && cache[i + 1][j-1]){
                    cache[i][j] = true;
                    if(end - start  < j-i){
                        start = i;
                        end = j;
                    }
                }else{
                    cache[i][j] = false;
                }
            }
        }
        return s.substring(start,end+1);
    }
}


回到顶部