最长回文子串

导语

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

暴力破解

确定最长回文子串 最暴力直接的方法将就是利用数学思维 类似判断长度为N的数中，存在多少个数。类似下面这样 。从左向右一个个拆分出来 ，就是最后的结果。这样子的时间复杂约为O（n)

[(sum_i=1)^n i = frac{n(n+1)}{2} ]

动图演示

暴力demo

class Solution {
    public static boolean IsPalindrome(String s){/* 判断是否回文*/
     char[] dest = s.toCharArray();/*字符串转数组便于数组转换*/
     int first,last;			/* 双指针确定回文*/
     first = 0;
     last = s.length()-1;
     while(first <= last){
         if(dest[first] != dest[last]) return false;
         first++;
         last--;
     }
     return true;

 }
    public String longestPalindrome(String s) {
        int max;
        int llength = s.length();
        int maxLength = 0;
        String maxPalindrome = "";
        for(int i = 0; i < llength; i++){
            for(int j = i+1; j <= llength; j++){
                String snew = s.substring(i,j);//substring 分割出一个字串 从第i个到j个 不包括j个元素
                if(IsPalindrome(snew)){
                    if(maxLength <= j-i) {
                        maxLength = j - i;
                        maxPalindrome = snew;
                    }
                }
            }
        }
        return maxPalindrome;
    }
}

注意事项

java中 静态方法不可以直接调用非静态方法：

例子：

public class Test1 {
    public String get()
    {
        return "123";
    }
    public static void main(String[] args)
    {
          String string =get();
    }
}

这样子是不行的

解决方法一：将get()函数变为static，将变量声明为全局静态的

public class Test1 {
    static String  string;
    public static String get()
    {
        return "123";
    }
    public static void main(String[] args)
    {
         string =get();
         System.out.print(string);
    }
}

方法二 创建这个数的对象

public class Test1 {
    public  String get() {
        return "123";
    }
    public static void main(String[] args) {
        Test1 c = new Test1();
        String string = c.get();
        System.out.print(string);
    }
}

个人总结

暴力破解 本身是不难的，难的是在编程的时候注意。第一开始编程的时候，对于小细节考虑的不是很多。比如substring方法中提示了如何这个方法分割出子字符串，最终确定相应得结果。还有就是关于循环得方式，最最需要确定就是，循环多少次以及最后需要结束条件。尤其是对尾部得判断，导致自己像个傻逼，以后还请注意

2020-4-12所写

---

中心扩展算法

同样是利用回文子串的对称性，找出所有的回文中心。回文中心分别向左右两边扩展。每个回文中心结束后进行一次最大长度比较，记录最大长度的子串和字符起点和终点。回文中心有2*n-1个，之所以不是 n 个，是因为其子串的长度即可能是奇数，也可能是偶数。

• 奇回文中心是一个字符
• 偶回文中心是两个字符

如果判定奇偶呢？或者是统一处理呢。

列出表格比较容易判断。列出一个长度为3的字符串内容的表格，其中内容分别是中心的左起始点和右终止点。

编号i	回文的左起始位置(l_i)	回文右起始位置(l_r)
0	0	0
1	0	1
2	1	1
3	1	2
4	2	2

这就是(2n - 1)个中心,([l_i,r_i])。在这种情况下 (l_i)等于i/2向下取整，(r_i = l_i + (i mod 2)).

所以此时只需要从0 到 2n -2 遍历i即可，就可以得到所有的回文中心了。因为无论是奇数，还是偶数，都可以统一地遍历起来了

中心扩展demo

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";

        char[] ch = s.toCharArray();
        //存储最大值，和坐标
        int[] m = new int[3];

        for(int i = 0; i < 2 * n - 1; i++){

            int l = i / 2;
            int r = l + i % 2; // 左右边界统一处理
            while ( l >=0 && r < n && ch[l] == ch[r]){
                l--;
                r++;
            }

            int length = r - l + 1;
            if(length > m[0]){
                m[0] = length;
                m[1] = l + 1;
                m[2] = r - 1;
            }
        }
        return s.substring(m[1], m[2] + 1);
    }
}

2020 08 19 更新

---