5. Longest Palindromic Substring

APICloud 發(fā)布于2019-08-14 17:57 / 2811人閱讀

摘要：暴力算法就是找到所有每個(gè)都進(jìn)行的檢查。時(shí)間復(fù)雜度是個(gè)調(diào)用平均時(shí)長(zhǎng)為這里唯一確定用的是頭尾表示。因?yàn)榈膶?duì)稱性，我們可以從中間出發(fā)向兩邊延展，找到最長(zhǎng)的分為兩種基本情況。奇數(shù)長(zhǎng)度出發(fā)點(diǎn)一致，都為偶數(shù)長(zhǎng)度出發(fā)點(diǎn)為相鄰的點(diǎn)，和結(jié)束是

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

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

暴力算法就是找到所有substring, 每個(gè)都進(jìn)行isPalindrome的檢查。時(shí)間復(fù)雜度是O(N^3). N^2個(gè)substring, 調(diào)用isPalindrome平均時(shí)長(zhǎng)為O(N).
這里唯一確定substring用的是頭尾(i,j)表示。因?yàn)閜alindrome的對(duì)稱性，我們可以從中間出發(fā)向兩邊延展，找到最長(zhǎng)的palindrome.
分為ABA, ABBA兩種基本情況。一共有N個(gè)位置唯一標(biāo)記點(diǎn)，調(diào)用一次extenPalindrome時(shí)間worst case是O(len)，
最大也就是中點(diǎn)位置的O(n/2). 總的時(shí)間復(fù)雜度大致為O(N^2/4)

另外還有一種方法，想法來自于palindrome partition那題。 用一個(gè)boolean[i,j]表示(i,j)是否為palindrome, 
比較i-1和j+1. 寫過一個(gè)，代碼復(fù)雜，跑起來特別慢，特別是"aaaaaaa"這種，所以拋棄掉。

public class Solution {
    private int lo = 0, maxLen = 0;
    
    public String longestPalindrome(String s) {
        if(s.isEmpty()) return null;
        int len = s.length();
        if(len < 2) return s;
        
        for(int i=0; i= 0 && k < s.length() && s.charAt(j) == s.charAt(k)){
            j--;
            k++;
        }
        // 結(jié)束是s(j)!=s(k)
        // k-1 - (j+1) +1 = k - j -1
        if(maxLen < k - j - 1){
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}