Leetcode - Longest Palindromic S

Question:

Paste_Image.png

My code:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return null;
        int max = 1;  // assume that every single character is palindrome
        String longestStr = "" + s.charAt(0);
        for (int i = 0; i < s.length() - 1; i++) {
            String s1 = getP(s, i, i);
            if (max < s1.length()) {
                max = s1.length();
                longestStr = s1;
            }
            String s2 = getP(s, i, i + 1);
            if (max < s2.length()) {
                max = s2.length();
                longestStr = s2;
            }
        }
        return longestStr;
    }
    
    private String getP(String s, int head, int tail) {
        int i = head;
        int j = tail;
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
    
    
    public static void main(String[] args) {
        Solution test = new Solution();
        String a = "abb";
        System.out.println(test.longestPalindrome(a));
    }
}

My test result:

Paste_Image.png

这次题目做了好久。。。每次都是时间测试过不了。
第一次我使用了自己的算法。用一个哈希数组来处理。
我的做法是申请一个二维数组：

Paste_Image.png

用来标志每个字符在字符串中出现的index。这个二维数组的功能相当于一个哈希表。所以首先需要遍历下字符串，复杂度是 O(n)，构造这个二维数组。然后再次遍历整个字符串。比如遍历到的是 'a'，就去二维数组中直接定位到存放'a'的那个内存块。然后判断所有这些位置是否能构成回环。因为开头是'a'的回环字符串，其结尾也一定是'a'。所以用这个二维数组充当哈希表，快速的找出该字母在字符串中出现的位置，然后判断这些情况是否构成回环。

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return null;
        int max = 1;  // assume that every single character is palindrome
        String longestStr = "" + s.charAt(0);
        int[][] hashArray = new int[256][s.length()];  // to state the index of every character in this string
        int[] frequency = new int[256];  // to state the times that every character comes up
        for (int i = 0; i < s.length(); i++)
            hashArray[s.charAt(i)][frequency[s.charAt(i)]++] = i;
        for (int i = 0; i < s.length(); i++) {
            for (int j = frequency[s.charAt(i)] - 1; j >= 0; j--) {
                if (i >= hashArray[s.charAt(i)][j])
                    continue;
                else {
                    if (isPalindrome(s, i, hashArray[s.charAt(i)][j])) {
                        if (hashArray[s.charAt(i)][j] - i + 1 > max) {
                            max = hashArray[s.charAt(i)][j] - i + 1;
                            longestStr = s.substring(i, hashArray[s.charAt(i)][j] + 1);
                            break;
                        }
                    }
                        
                }
            }
            if (max >= s.length() - i)
                break;
        }
        return longestStr;
    }
    
    private boolean isPalindrome (String s, int head, int tail) {
        if (head < 0 || head >= s.length() || tail < 0 || tail >= s.length())
            return false;
        int i = head;
        int j = tail;
        while (i <= j) {
            if (s.charAt(i) != s.charAt(j))
                return false;
            else {
                i++;
                j--;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        String a = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
        System.out.println(test.longestPalindrome(a));
    }
}

然后时间测试过不了。
于是我参考了网上的做法，使用DP。
具体代码：

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return null;
        int max = 1;  // assume that every single character is palindrome
        String longestStr = "" + s.charAt(0);
        int left = 0;
        int right = 1;
        boolean[][] isPal = new boolean[1000][1000];
        for (int i = 0; i < s.length(); i++)
            isPal[i][i] = true;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                isPal[i][i + 1] = true;
                left = i;
                right = i + 1;
            }
        }
        for (int len = 3; len < s.length(); len++) {
            for (int i = 0; i < s.length() - len + 1; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && isPal[i + 1][j - 1]) {
                    isPal[i][j] = true;
                    left = i;
                    right = j + 1;
                }
            }
        }
        
        return s.substring(left, right);
        
        
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        String a = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        System.out.println(test.longestPalindrome(a));
    }
}

时间测试过不了，于是我采用了最上面的那个方法。
其实还有一个O（n）复杂度的方法，今晚太累，看不动了，以后有机会再研究。
这四个方法在两篇别人的日志里写的很好，链接如下
https://github.com/xiangzhai/leetcode/blob/master/question/longest-palindromic-substring-part-i.md

https://github.com/xiangzhai/leetcode/blob/master/question/longest-palindromic-substring-part-ii.md

有兴趣的可以具体看下。

**
总结: 妈了个逼的真恶心。。。
然后，我想说，其实申明数组也是很花时间的。
比如说，我觉得第二个做法过不了时间测试而第三个可以过的原因就是，第二个做法申明了一个二维数组。
a[1000][1000].申明这个数组的时候，编译器会自动执行

for (int i = 0; i < 1000; i++)
    for (int j = 0; j < 1000; j++)
         a[i][j] = 0;

会花费一些时间。
然后经确认， s.charAt(i) 复杂度是 O(1)
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return s;
        int maxLen = Integer.MIN_VALUE;
        String maxStr = null;
        for (int i = 0; i < s.length(); i++) {
            /** choose i as center, move left and right: (pre, post) */
            int pre = i - 1;
            int post = i + 1;
            while (pre >= 0 && post < s.length() && s.charAt(pre) == s.charAt(post)) {
                pre--;
                post++;
            }
            if (post - pre - 1 > maxLen) {
                maxLen = post - pre - 1;
                maxStr = s.substring(pre + 1, post);
            }
            /** choose i, i+1 as center, move left and right: (pre, post) */
            pre = i;
            post = i + 1;
            while (pre >= 0 && post < s.length() && s.charAt(pre) == s.charAt(post)) {
                pre--;
                post++;
            }
            if (post - pre - 1 > maxLen) {
                maxLen = post - pre - 1;
                maxStr = s.substring(pre + 1, post);
            }
            if (maxLen == s.length())
                break;
        }
        return maxStr;
    }
}

这个作法的思想就是以i为中点，向左右扩散。
然后有两种可能。
(..., i - 1, i, i + 1, ....)
(..., i - 1, i , i + 1, i + 2, ....)
然后判断下，如果已经达到了最大值，就直接退出循环了。
复杂度是O(n^2)

第二种做法：
My code:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return s;
        int maxLen = Integer.MIN_VALUE;
        String maxStr = null;
        int[][] tracker = new int[s.length()][s.length()];
        /** for palindromic string with length 1 */
        for (int i = 0; i < s.length(); i++)
            tracker[i][i] = 1;
        /** for palindromic string with length 2 */
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i - 1) == s.charAt(i)) {
                tracker[i - 1][i] = 1;
                maxLen = 2;
                maxStr = s.substring(i - 1, i + 1);
            }
        }
        /** for palindromic string with length >= 3, <= s.length() 
        * if tracker[i + 1][i + j - 1] == 1 and s.charAt(i) == s.charAt(i + j) => tracker[i][i + j] = 1;
        */
        for (int j = 2; j < s.length(); j++) {
            for (int i = 0; i + j < s.length(); i++) {
                if (tracker[i + 1][i + j - 1] == 1 && s.charAt(i) == s.charAt(i + j)) {
                    tracker[i][i + j] = 1;
                    if (maxLen < j + 1) {
                        maxLen = j + 1;
                        maxStr = s.substring(i, i + j + 1);
                    }
                }
            }
        }
        return maxStr;
    }
}

DP. 设置一个二维矩阵，一层层推进过去。
但是，时间测试过不了。因为他的复杂度一定是 n ^ 2
而上一种做法，系数可能会小很多，所以过了测试。

还有种做法复杂度是 O(n), 就不研究了。
参考网址：
http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        int len = s.length();
        int maxLen = 1;
        String ret = "" + s.charAt(0);
        for (int i = 0; i < len; i++) {
            int begin = i;
            int end = i;
            while (begin - 1 >= 0 && end + 1 < len && s.charAt(begin - 1) == s.charAt(end + 1)) {
                begin--;
                end++;
            }
            if (maxLen < end - begin + 1) {
                maxLen = end - begin + 1;
                ret = s.substring(begin, end + 1);
            }
            
            begin = i;
            end = i + 1;
            while (begin >= 0 && end < len && s.charAt(begin) == s.charAt(end)) {
                begin--;
                end++;
            }
            if (maxLen < end - begin - 1) {
                maxLen = end - begin - 1;
                ret = s.substring(begin + 1, end);
            }
        }
        
        return ret;
    }
}

第一种中间扩散的方法，和上面的一样，不多写了。
然后DP做法，其实很简单，我想的过于复杂了。

My code:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int maxLen = 0;
        String ret = "" + s.charAt(0);
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = 0; i < len - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                maxLen = 2;
                ret = s.substring(i, i + 2);
            }
        }
        
        for (int k = 3; k <= len; k++) {
            for (int i = 0; i <= len - k; i++) {
                int j = i + k - 1;
                if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        ret = s.substring(i, j + 1);
                    }
                }
            }
        }
        
        return ret;
    }
}

其实只是起到了 memcache 的作用。

Anyway, Good luck, Richardo! -- 09/18/2016