5. Longest Palindromic Substring

难度: Medium

题目描述

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

解题思路

代码实现

解决方案

java

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) {
                return s;
            }
            return s.substring(0, 1);
        }

        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        int maxLen = 0;
        String res = s.substring(0,1);

        for (int len = 2; len <= s.length(); len++) {

            for (int left = 0; left < s.length(); left++) {
                int right = left + len - 1;
                if (right >= s.length()) {
                    break;
                }

                if (s.charAt(left) == s.charAt(right)) {
                    if (right - left < 3) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }
                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    res = s.substring(left, right+1);

                }

            }
        }

        return res;

    }
}