一次面试，回文字符串的实现

记一次面试：求一个字符串的最大回文子字符串

1.回文字符串的分类

1.1 单核回文 abcba

1.2 双核回文 abccba

2 解题方法

2.1 暴力求解

 /**
     * 暴力求解
     * 1.遍历字符串，
     * 2，判断其子字符串是否回文，这里的子字符串是依次减少的
     * 3.如果回文，就结束循环，返回最长的回文字符串
     * 时间复杂度On3(有点高)
     */
    public static String longestPalindrome(String str){
       
       if (str.length() <= 1) {
            return str;
        }
        
        for (int i = str.length(); i > 0; i--) {
            for (int j = 0;  j<str.length()-i-1; j++) {
                String sub = str.substring(j,i+j); // 得到子字符串
                int count = 0;
                
                // 判断是否回文
                for (int k = 0; k <sub.length()/2 ; k++) {
                    if(sub.charAt(k) == sub.charAt(sub.length()-k-1)){
                        count++;
                    }
                }
                if(count == sub.length()/2){
                    return sub;
                }
            }
        }
        return ""; // 没有找到最长的字符串
    }
    

2.2 声明两个高低指针，找到回文字符串的核，然后向两边扩展

 /**
    1）将子串分为单核和双核的情况，单核即指子串长度为奇数，双核则为偶数；

    2）遍历每个除最后一个位置的字符index(字符位置)，单核：初始low = 初始high = index，low和high均不超过原字符串的下限和上限；判断low和high处的字符是否相等，相等则low++、high++（双核：初始high = 初始low+1 = index + 1）；

    3）每次low与high处的字符相等时，都将当前最长的回文子串长度与high-low+1比较。后者大时，将最长的回文子串改为low与high之间的；

    4）重复执行2）、3），直至high-low+1 等于原字符串长度或者遍历到最后一个字符，取当前截取到的回文子串，该子串即为最长的回文子串。
     */
    public static String longestPalindrome1(String str){

        if(str.length() <= 1){
            return str;
        }
        for (int i = 0; i < str.length()-1; i++) {
            findLongPlaindrome(str,i,i); // 单核
            findLongPlaindrome(str,i,i+1);  // 双核
        }
        return sub;
    }

    /**
     * 核心思想是声明两个指针，找到这个回文字符串的核，然后向两边外扩展
     * @param str 目标字符串
     * @param low 低指针
     * @param high 高指针
     */
    private static void findLongPlaindrome(String str, int low, int high) {
        while(low >= 0 && high <= str.length()-1){
            if(str.charAt(low) == str.charAt(high)){
                if(high-low+1 > maxLength){
                    maxLength = high-low+1;
                    sub = str.substring(low, high + 1);
                }
                low--;
                high++;
            }else{
                break;
            }
        }

    }

3 测试

   public static void main(String[] args) {
        String test = "abcbadefg";
        test = FindMaxLengthSubString.longestPalindrome(test);
        //test = FindMaxLengthSubString.longestPalindrome1(test);
        System.out.println(test);
    }

结果

 abcba

参考
https://blog.csdn.net/qq_32354501/article/details/80084325