最长回文子串解法

针对一个字符串,返回长度最大的回文子串

例:"abcb" ===> "bcb"
     "abab" ===> "aba","bab"

在中间添加#是为了处理回文子串长度为偶数时,不能同时向两边拓展的尴尬,例如回文子串为"oo",就会难以用下面的逻辑处理.

 画了上面这个示意图,应该挺好理解的.

import java.util.ArrayList;

public class leecode {
    public static void main(String[] args) {
        String str1 = "abaHelloll";
        String str2 = "abc";
        System.out.println("answer is "+findMaxStr(str1));
        System.out.println("answer is "+findMaxStr(str2));
    }
    public static ArrayList findMaxStr(String str){
        //为了保证字符串为单数,我们在字符串相邻的两个字符间插入"#"
        //原str的lenth为len,插入的"#"的个数即为len-1
        //现新字符串的lenth即为2len-1,必定是单数
        //解决了面对单双数长度的回文子串的复杂逻辑处理
        StringBuilder new_str = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            new_str.append(str.charAt(i));
            if (i != str.length() - 1){
                new_str.append("#");
            }
        }
        //现在得到的就是插入#的字符串
        str = new_str.toString();
        ArrayList all_ans = new ArrayList<>();
        System.out.println("处理后的字符串: " + str);
        //创建一个ans,用于收集结果
        StringBuilder ans;
        //max_str用于暂存目前最长的回文子串
        String max_str = "";
        //max_size用于暂存目前最大的回文子串长度
        int max_size = 1;
        //这个n代表偏移量
        int n;
        //以str中每一个元素为中心点,向两边查找.
        // TODO: 2021/12/15 在循环中,出现+=2的情况,一般就是为了处理'#',
        //  '#' 作为中心点 没有意义
        for (int i = 0; i < str.length(); i+=2) {
            //每次更换中心点时,给偏移量和ans赋初值
            n = 2;
            ans = new StringBuilder();
            ans.append(str.charAt(i));
            //例如 : 1  #  2  #  1     当i遍历到'2'时,向两边以n为长度来查询是否有相同的元素
            //伪代码:                   if: str.charAt('2'的下标 - n) == str.charAt('2'的下标 + n)
            //如果满足,则偏移量+1,继续匹配
            // TODO: 2021/12/15 这里n+=2,是为了跳过两个有效字符间的# 
            while ((i - n) >= 0 && (i + n) < str.length() && str.charAt(i - n) == str.charAt(i + n)) {
                ans = new StringBuilder(str.charAt(i-n) + ans.toString() + str.charAt(i+n));
                n+=2;
            }
            //如果不满足,去比较已得的子串是否比之前得到的大,
            //然后i++,以下一个元素为中心点,再次开始向两侧查找
            if (ans.toString().length() > max_size){
                all_ans.clear();
                max_size = ans.toString().length();
                max_str = ans.toString();
                all_ans.add(max_str);
            }else if (ans.toString().length() == max_size){
                max_str = ans.toString();
                all_ans.add(max_str);
            }
        }
        return all_ans;
    }
}