[LeetCode] 5. Longest Palindromi

Welcome To My Blog

5. Longest Palindromic Substring (medium)

5.1.png

Brute force

找出所有可能的子串(窗口),O(n^{2),再判断是否为回文,O(n}2),所以总的时间复杂度为O(n^3),Time Limit Exceeded

Dynamic Programming

5.2.png

1. 用递归的方式实现P(i,j)会导致 Time Limit Exceeded
   能不能借用HashMap实现,有待考虑

//递归实现P(i,j)
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length(),len = 0,start = 0;
        for (int i = 0; i < n; i++){
            for (int j = i ;j >= 0; j--){
                if(P(s,j,i) && ((i - j + 1) > len)){
                    start = j;
                    len = i - j + 1;
                }
            }
        }
        return s.substring(start,start + len);
    }
    private boolean P(String s,int i, int j){
        if (i == j) return true;
        if (i +1 == j) return s.charAt(i) == s.charAt(j);
        return (P(s,i+1,j-1) && s.charAt(i) == s.charAt(j));
    }
}

2. 使用循环实现P(i,j)
3. complexity analysis:
   • time complexity: O(n^2)
   • space complexity: O(n^2)

//循环实现
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length(),len = 0,start = 0;
        boolean[][] dynamic_prog = new boolean[n][n];
        for (int i = 0; i < n; i++){
            for (int j = i; j>=0; j--){
                boolean temp = s.charAt(j)== s.charAt(i);
                //精髓就在于这步
                dynamic_prog[j][i] = (temp && (((i - j) < 3)||dynamic_prog[j + 1][i - 1]));
                if(dynamic_prog[j][i]&&((i - j + 1) > len)) {
                    start = j;
                    //最开始错写成i-j,因为s.substring(start,end)属于左闭右开形式
                    len = i - j + 1;
                }
            }
        }
        return s.substring(start,start + len);
}
}

循环示意图:

5.3.png
(j,i)构成了一个上三角矩阵,
黄圈表示(i-j)<2的状态,
当(i-j)=3时,p(j-1,i-1)处于对角线上,对角线上i=j,此时如果s_i==s_j则有p(i,j)=true
当(i-j)>3时,就要同时判断p(j-1,i-1)和s_i,s_j了
5.4.png

中心扩展

1. palindrome是轴对称的,对于n个元素,对称轴有2n-1种,其中n个元素可以作为n个对称轴,两个相同的元素也可以作为对称轴,eg:abba中的bb是对称轴,这样的元素可能有n-1个,故共有2n-1种可能.从对称轴向两边扩展,这个逻辑比起动态规划更直观
2. complexity analysis:
   • time complexity: O(n^2)
   • space complexity: O(1)

class Solution {
    public static String longestPalindrome(String s) {
        int n = s.length(), len1 = 0, len2 = 0;
        int res = 0, p = 0;
        if(n == 1) return s;
        for (int i = 0; i < n - 1; i++){
            //1. 对2n-1种可能的对称中心进行扩展
            //1.1 对称中心为1个元素
            len1 = expandAroundCenter(s,i,i);
            //1.2 对称中心为2个元素,前提:相邻两个元素相同
            if(s.charAt(i) == s.charAt(i + 1))
                len2 = expandAroundCenter(s,i,i + 1);
            //1.3 len1一定是奇数,len2一定是偶数,也可以利用这个条件
            if(len1 >= len2 && len1 > res){
                res = len1;
                p = i + (1-len1)/2;
            }
            else if(len1 < len2 && len2 > res){
                res = len2;
                p = i + 1 - len2/2;
            }
        }
        return s.substring(p,p+res);
    }
    public static int expandAroundCenter(String s, int l, int r){
        int n = s.length();
        while(l >= 0 && r < n && s.charAt(l)== s.charAt(r)){
            l--;
            r++;
        }
        return r - l - 1;
    }
}