美团一面笔试算法（3-1）面试，到店SASS 系统算法，最长回文子串

短命女 2022-12-29 14:07 82阅读 0赞

题目：

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

示例 1：

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

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

以下是我的代码：

public class Test19 {
            public static void main(String[] args) {
                String s = "abba:aaaaa";
                String maxLarege = "";
                //1.指针point 1
                int i = 0;
                int j = i;
                //2.指针point 2
                while (true) {
                        if(i >= s.length()){
                            break;
                        }
                        String str = s.substring(i, j);
                        //是否是回文子串
                        if (str.length() > 1 && reserve(str)) {
                            maxLarege = maxLarege.length() < str.length() ? str : maxLarege;
                        }
                        if(j >= s.length()) {
                            i++;
                            j = i+1;
                            continue;
                        }
                        j++;
                }
    
                System.out.println(maxLarege);
            }
            public static Boolean reserve(String s){
                int i = 0;
                int j = s.length()-1;
                while(true){
                    //
                    if(i == j || i>j){
                        break;
                    }
                    if(s.charAt(i)!=s.charAt(j)){
                        return false;
                    }
                    i++;
                    j--;
                }
                return true;
            }
    }

输出结果：

![20201222234903450.png][]

[20201222234903450.png]: /images/20221120/3c2248221c744026bf7075347b43b31d.png