编程练习-寻找最长回文串

又是很久没有练习了，前段时间的字节跳动和阿里笔试题，真的是惨绝人寰，这道题，难度定义为中等，又做了一个小时，哎，为秋招深深的担忧啊！

题目来源LeetCode

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

示例 1：

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

示例 2：

输入: “cbbd”
输出: “bb”

分析

从它的示例可以看出，回文分为两种，奇数长度的回文，偶数长度的回文！

• 思路

1. 奇回文：以正中间处的字符为中心，向两边展开。
2. 偶回文：以正中间处的两个字符为中心，向两边展开。

实现（java）

package com.jiajia.m4;

/**
 * @ClassName: LongestPalindromic
 * @Author: fanjiajia
 * @Date: 2019/4/25 下午7:32
 * @Version: 1.0
 * @Description: 求字符串最长回文串
 */
public class LongestPalindromic {

    public static void main(String[] args) {

        LongestPalindromic palindromic = new LongestPalindromic();
        String s = "aaabaaaa";
        System.out.println(palindromic.longestPalindrome(s));
    }

    public String longestPalindrome(String s) {
        String res_str = ""; // 结果串
        if(s == null || s.length() == 0) {
            return res_str;
        }else if(s.length() == 1) { // 长度为1的串
            res_str = s;
        }else {
            // 长度超过1
            /**
             * 循环遍历每一个字符，向两端伸展，这种是奇数回文串
             */
            int low, hight;
            for(int i = 0; i < s.length(); i++) {
                low = hight = i;
                while((--low) >= 0 && (++hight) < s.length() && s.charAt(low) == s.charAt(hight)) {

                }
                if(low >= 0 && hight < s.length()) {
                    // 说明low处的字符和hight处的字符不相等
                    if(res_str.length() < (((--hight) - (++low)) + 1)) {
                        res_str = s.substring(low, hight + 1);
                    }
                }else if(low < 0) {
                    // low率先出界
                    if(res_str.length() < ((hight) - (++low)) + 1) {
                            // low和hight相邻，需要判断二者是否相等
                            res_str = s.substring(low, hight + 1);
                    }
                }else {
                    // hight超出边界
                    if(res_str.length() < ((--hight) - (++low)) + 1) {
                            // low和hight相邻，需要判断二者是否相等
                            res_str = s.substring(low, hight + 1);
                    }
                }

                /**
                 * 循环遍历每一个字符，向两端伸展，偶数回文的查找
                 */
                low = i;
                hight = i+1;

                if(low == s.length() -1) {
                    break;
                }

                if(s.charAt(low) != s.charAt(hight)) {
                    // 正中间两个字符一定是相等的
                    continue;
                }

                while((--low) >= 0 && (++hight) < s.length() && s.charAt(low) == s.charAt(hight)) {

                }
                if(low >= 0 && hight < s.length()) {
                    // 说明low处的字符和hight处的字符不相等
                    if(res_str.length() < (((--hight) - (++low)) + 1)) {
                        if(hight - low != 1 || (hight - low == 1 && s.charAt(low) == s.charAt(hight))){
                            res_str = s.substring(low, hight + 1);
                        }
                    }
                }else if(low < 0) {
                    // low率先出界
                    if(res_str.length() < ((hight) - (++low)) + 1) {
                        if(hight - low != 1 || (hight - low == 1 && s.charAt(low) == s.charAt(hight))){
                            res_str = s.substring(low, hight + 1);
                        }

                    }
                }else {
                    // hight超出边界
                    if(res_str.length() < ((--hight) - (++low)) + 1) {
                        if(hight - low != 1 || (hight - low == 1 && s.charAt(low) == s.charAt(hight))){
                            res_str = s.substring(low, hight + 1);
                        }
                    }
                }
            }
        }
        return res_str;
    }
}

1. 一定要注意在i定位到字符串最后一位时，也即此时不可能再出现偶数回文了，需要break，否则会存在案例比如ac导致数组下标越界错误！
2. 偶回文时，正中间两个一定是相等的。
3. while循环中，如果前面返回false，那么后面的判断将不会执行，所以–low和hight++并不是都会执行。
4. substring(beginIndex, endIndex)并不包含endIndex处的字符（多么基础的领悟）！

   最后

   此致，敬礼