5. Longest Palindromic Substring

Question:

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"

Thinking:

• Method1: Iterate center of two points. ** 1.Center is a character, length of palindromic string is odd. ** 2.Center is between two characters, length of palindromic is even.

    class Solution {
        public String longestPalindrome(String s) {
            int start = 0;
            int maxLen = 0;
            int slen = s.length();
            if(slen <= 1) return s;
            for(int i = 0; i < slen; i++){
                int len = 1;
                while(i - len >= 0 && i + len < slen){	//for palindromic centered at one point
                    if(s.charAt(i - len) == (s.charAt(i + len))){
                        if(maxLen < 2 * len + 1){
                            maxLen = 2 * len + 1;
                            start = i - len;
                        }
                    }else{
                        break;
                    }
                    len++;
                }
                //For palindromic centered between characters
                len = 1;
                while(i - len + 1 >= 0 && i + len < slen){
                    if(s.charAt(i - len + 1) == s.charAt(i + len)){
                        if(maxLen < 2 * len){
                            maxLen = 2 * len;
                            start = i + 1 - len;
                        }
                    }else{
                        break;
                    }
                    len++;
                }
            }
            if(maxLen == 0){
                return s.substring(0,1);
            }
            return s.substring(start, start+maxLen);
        }
    }
  

二刷

1. 将检查回文的方法封装起来。

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;
        String res = "";
        for(int i = 0; i <= s.length() - Math.max(1, res.length()); i++){
            for(int j = i + Math.max(1, res.length()); j <= s.length(); j++){
                String temp = s.substring(i, j);
                if(check(temp))
                    res = temp;
            }
        }
        return res;
    }
    private boolean check(String s){
        int low = 0, high = s.length() - 1;
        while(low < high){
            if(s.charAt(low++) != s.charAt(high--))
                return false;
        }
        return true;
    }
}

1. 双边插值
   • 对于奇数情况，传入当前的index。
   • 对于偶数情况，传入index和index+1。

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;
        String result = "";
        for(int i = 0; i < s.length(); i++){
            String res1 = expandAroundCenter(s, i, i);
            String res2 = expandAroundCenter(s, i, i + 1);
            String res = res1.length() > res2.length() ? res1: res2;
            result = res.length() > result.length() ? res: result;
        }
        return result;
    }
    private String expandAroundCenter(String s, int low, int high){
        if(high >= s.length() || s.charAt(low) != s.charAt(high)) return s.substring(low, high);
        while(low >=0 && high < s.length() && s.charAt(low) == s.charAt(high)){
            low--;
            high++;
        }
        return s.substring(++low, high);
    }
}