letcode 5 最长回文子串

求一个字符串的最长回文子串

我发现letcode好像不限制执行时间?

这个题有个技巧:在每个字符两边添加一个无关字符: aba -> *a*b*a*; abba->*a*b*b*a* .这样就会得到一个恒为奇数串的字符串.

然后有两种解法:

　　1) 以每个字符为中心,向两边最大扩展 O(n^2)

        int n = s.length();
        StringBuilder str = new StringBuilder(s);
        StringBuilder addStr = new StringBuilder(2*n+5);
        addStr.append('#');
        for(int i=0;i<n;i++){
            addStr.append(s.charAt(i));
            addStr.append('#');
        }
        //System.out.println(addStr);
        int max = 1;
        int maxL = 0;
        int maxR = 0;
        int maxC = -1;
        int len = addStr.length();
        for(int i =0;i<len;i++){
            for(int pl =i-1,pr=i+1;pl>-1&&pr<len;pl--,pr++){
                if(addStr.charAt(pl)==addStr.charAt(pr)){
                    if(max<(pr-pl+1)){
                        max = pr-pl+1;
                        maxL=pl;
                        maxR=pr;
                        maxC=i;
                    }
                    continue;
                }
                break;
            }
        }

        StringBuilder res1 = new StringBuilder(addStr.substring(maxL,maxR+1));
        StringBuilder res = new StringBuilder();
        for(int i=0;i<res1.length();i++){
            if(i%2!=0) res.append(res1.charAt(i));
        }
        s=res.toString();
        return s;

　　2) 马拉车算法   O(n)

为了防止在暴力扩展的时候越界,我们在 扩展之后的字符串两端,各加一个 $ 和 % 使得while必然终止.

p[i]:以第i个字符为中心的回文串的最大长度

id: 当前最长的回文串的中心

mx: 当前最大回文串的右边界

当我们计算以第i个字符为中心的最大回文子串时,如果它在回文串(id)内部, 则p[i] = Math.min(p[2*id-i],mx-i),否则设置为1.

当i在id内部,i<mx . 2*id-i 是它关于id的对称位置.  假如mx-i> p[2*id-i] ,则 p[i]=p[2*id-i] ,否则 p[i]=mx-i;

        int n = s.length();
        StringBuilder str = new StringBuilder(s);
        StringBuilder addStr = new StringBuilder(2*n+5);
        addStr.append("$#");
        for(int i=0;i<n;i++){
            addStr.append(s.charAt(i));
            addStr.append('#');
        }
        addStr.append('%');
        int len = addStr.length();
        int[] p = new int[len];
        int id=0,mx=0;
        for(int i =1;i<len-1;i++){
            if(i<mx) p[i] = Math.min(p[2*id-i],mx-i);
            else p[i]=1;
            while (addStr.charAt(i-p[i])==addStr.charAt(i+p[i])) p[i]++;
            if(i+p[i]>mx){
                mx=i+p[i];
                id=i;
            }
        }
        int maxInd=-1;
        int maxNum = -1;
        for(int i=0;i<len;i++){
            if(p[i]>maxNum){
                maxInd=i;
                maxNum=p[i];
            }
        }
        String res1 = addStr.substring(maxInd-maxNum+1,maxInd+maxNum);
        StringBuilder res = new StringBuilder();
        for(int i=1;i<res1.length();i++)
            if(i%2==1) res.append(res1.charAt(i));
        return res.toString();