Leetcode第五題_Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Leetcode第5題，題目大概意思是給一個字元串，從中找出最長的回文串，所謂回文串，就是“我愛你你愛我”這樣從前從後讀起來都是一樣的東西啦。

我想到大概解題思路是這樣的，從頭尾開始，依次比較，如果相同就頭增尾減。如果不同，尾節點左移，直到與頭尾碰面。這就找到了從該頭結點出發的回文串，然後頭結點右移，尋找下一結點開始的回文串。雖然時間複雜度達到了驚人的O(n*n)，但我猜應該還是能夠AC的。

public static String longestPalindrome(String s) {
    int i = 0;
    int j = s.length()-1;
    int k = 0;
    int k2 = 0;
    int max = 0;
    String r = s.substring(0,1);
    int flag = 1;
    while( k<s.length()){
        k = i;
        for (k2 = j; k2 > k; k2--) {
            if (s.charAt(k) == s.charAt(k2)) {
                k++;
                flag = 1;
            }
//              字元不相同則頭結點歸位，尾節點右移一個
            else {
                flag = 0;
                k = i;
                j--;
                k2 = j;
                k2++;
            }
        }
//          找到一個回文串，判斷是否最長，最長則存儲
        if (flag!=0 && j-i+1>max) {
            max = j-i+1;
            r = s.substring(i, j+1);
        }
//          頭結點右移
        i++;
        j = s.length()-1;
    }
    return r;
}
           

哎，弄了好久才把case測試對，結果最後告訴我逾時，我也是太天真，O（n*n）的也敢搞一搞。

實在想不出來了怎麼改進了，去看了下Leetcode的文章，果然大神就是碾壓啊。

articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

還有用字尾樹實作的。

http://blog.csdn.net/g9yuayon/article/details/2574781