5.Longest Palindromic Substring

Description

	#5	Longest Palindromic Substring	Medium
		Dynamic Programming	Top 150
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"

Solution

2D DP

Runtime 291ms		Memory 55.82MB

class Solution {
    private int[][] dp;
    private String s;
    public String longestPalindrome(String s) {
        this.s = s;
        this.dp = new int[s.length()][s.length()];
        for(int[] temp: dp)
            Arrays.fill(temp, -1);

        int max = 1, start = 0, end = 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i+1; j < s.length(); j++) {
                if(isPalindromic(i, j) && (j - i + 1 > max)) {
                    max = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end+1);
    }

    private boolean isPalindromic(int start, int end) {
        if(start >= end)
            return true;
        if(dp[start][end] != -1)
            return dp[start][end] == 1;
        boolean isPalindromic = (s.charAt(start) == s.charAt(end)) && isPalindromic(start+1, end -1); 
        dp[start][end] =  isPalindromic ? 1: 0;
        return isPalindromic;
    }
}

优化后：

Runtime 197ms		Memory 55.77MB

class Solution {
    public String longestPalindrome(String s) {
        /**
            s= babad
            1 0 1 0 0 bab
            # 1 0 1 0 aba
            # # 1 0 0 
            # # # 1 0 
            # # # # 1
         */
        int [][] dp = new int[s.length()][s.length()];
        for(int[] temp: dp)
            Arrays.fill(temp, -1);
        int max=1, start=0, end=0;
        for(int k = 1; k <= s.length(); k++){
            for(int i = 0; i < s.length(); i++) {
                int j = i + k - 1;
                if(j >= s.length())
                    break;
                if(i == j) dp[i][j] = 1;
                else if(s.charAt(i)  == s.charAt(j)){
                    dp[i][j] = i + 1 > j -1 || dp[i+1][j-1] == 1 ? 1: 0;
                    if(dp[i][j] == 1 && k > max) {
                        start = i;
                        end = j;
                        max = k;
                    }
                } else dp[i][j] = 0;
            }
        }
        // for(int i = 0; i < s.length(); i++) {
        //     for(int j = 0; j < s.length(); j++) {
        //         System.out.print(dp[i][j] == -1? "#": dp[i][j]);
        //         System.out.print(" ");
        //     }
        //     System.out.println();
        // }
        return s.substring(start, end + 1);
    }
}

Two Pointers

Runtime 5ms		Memory 40.92MB

class Solution {
    /* https://leetcode.com/problems/longest-palindromic-substring/solutions/4001583/simple-and-best-solution/ */
    private int start;  // 起始位置
    private int max;    // 最大长度

    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;

        start = 0;
        max = 0;
        // toCharArray 比charAt少了边界检查，会更快一些
        char[] chars = s.toCharArray();

        for(int i = 0; i < chars.length; i++){
            findPalindrome(chars, i, i);    // 以i为中心，奇数长度
            findPalindrome(chars, i, i+1);  // 以i为中心，偶数长度
        }
        return s.substring(start, start + max);
    }

    private void findPalindrome(char[] chars, int i, int j) {
        while(i >= 0 && j < chars.length && chars[i] == chars[j]){
            i--;
            j++;
        }
        int len = j - i - 1;
        if(len > max) {
            max = len;
            start = i + 1;
        }
    } 
}