前言

最近准备把算法慢慢的捡起来，所以准备日更一道算法题目，难度自然是由简入难，所以同学们可以每天都来看看小编的更新。日更时间定在每晚20:00，希望大家多多关注啦。昨天就欠更了，简直就是打脸。过完年刚开工，比较忙，今天更新两道，晚上还会更新一道!!!!!

寻找最长回文子串

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

例1：

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

例2：

输入： “cbbd” 输出： “bb”

解题思路

我们先说一下什么是回文串：简单的来说，回文串就是某一个字符串左右对称即为回文串。那么回文子串也就是在某一字符串中，包含的回文串。我们如何判断或者是寻找回文串呢？我们了解到他具有左右对称的性质，当我们要确认某一个字符串是否为回文串时，我们可以从字符串的中心开始，向左右两边进行对比。贴一段代码：

// 验证是否为回文串private boolean check(String s, int j, int k) { // s:字符串 j:中心下标 k:中心下标。  // 当字符串长度为奇数时，j=k // 当字符串长度为偶数是，j=k-1 while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) { j--; k++; } // 判断是否两边循环到了开始和结尾。 if(j==0&&k==s.length()-1){ return true; } return false;}

public class Test { private int start=0; // 定义回文串开始下标 private int maxLen=0; // 定义回文串最大长度  @Test public void test(){ // 输出答案 System.out.println(longestPalindrome("babad")); }  public String longestPalindrome(String s) { // 定义字符长度 int len = s.length(); // 判断长度如果小于2，即等于0或1，则直接返回当前字符串 if (len < 2) return s; // 定义循环，即将i作为回文串的中心进行查找或验证。 for (int i = 0; i < len - 1; i++) { // 假设答案回文串长度为奇数 findPalindrome(s, i, i);  // 假设答案回文串长度为偶数 findPalindrome(s, i, i + 1);  } // 从字符串中截取答案回文串 return s.substring(start, start + maxLen); } // 查找回文串 private void findPalindrome(String s, int j, int k) { // 以对称中心向左右比对字符以寻找回文串 while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) { j--; k++; } //（k - j - 1）是本次查询获得的回文串长度 if (maxLen < k - j - 1) { // 修改回文串开始下标 start = j + 1; // 修改最大长度 maxLen = k - j - 1; } }}

最后说两句

所有的题目都有很多种解法，我的一定不是最好的，甚至可以说是比较低端的解法，希望大牛们多多指教！！！如果朋友们对算法、编程有很大兴趣的话，可以私信我，大家一同探讨；相互学习、共同进步。朋友们如果对这道题目有更好的解法，希望可以在评论中指出，让大家一起讨论学习。最后感谢大家的阅读以及关注，谢谢大家！！！