5. Longest Palindromic Substring

Link

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"

Solution

DP

設計填寫迴圈的規則是，新的Loop要使用到舊的loop

-> you have to let the start index from the end of the array

 public String longestPalindrome(String s) {
        int N = s.length();
         if (s.length() <= 1)
            return s;
        boolean[][] dp = new boolean[N][N];
        for(int i = 0; i < N; i++){
            dp[i][i] = true;
        }
        int longestPalindromeStart = 0, longestPalindromeLength = 1;

        //因為希望lo是最右
        for(int lo = N-1; lo >= 0; lo--){
            for(int hi = i+1; hi < N; hi++){
                
                if(s.charAt(lo) == s.charAt(hi)){
                    if(hi - lo == 1 || dp[lo+1][hi-1]){
                        dp[lo][hi] = true;
                        if(hi - lo + 1 > longestPalindromeLength){
                            longestPalindromeStart = lo;
                            longestPalindromeLength = hi - lo + 1;
                        }
                    }
                }
                else{
                    dp[lo][hi] = false;
                }
            }
        }
        return s.substring(longestPalindromeStart, longestPalindromeStart + longestPalindromeLength);
    }

Expended each char

• Time complexity : O(n^2). Since expanding a palindrome around its center could take O(n)O(n) time, the overall complexity is O(n^2).

• Space complexity : O(1)

  int low = 0;
    int maxLen = 0;
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;
        for(int i = 0; i < len; i++){
            tryExtend(s, i, i); //assume the palindrome substring length is odd
            tryExtend(s, i, i+1); //assume the palindrome substring length is even
        }
        return s.substring(low, low+maxLen);
    }
    
    public void tryExtend(String s, int left, int right){
        
        char[] chars = s.toCharArray();
        while(left >= 0 && right < chars.length && chars[left] == chars[right]){
            left--;
            right++;
        }
        if(maxLen < right - left - 1){
            low = left + 1;
            maxLen = right - left -1;
        }
    }