欢迎大家关注我的以下主页，尤其是今日头条！！！谢谢🙏🙏🙏
csdn：雷园的csdn博客
个人博客：雷园的个人博客
简书：雷园的简书
今日头条：来自底层程序员的仰望
前言
- 最近准备把算法慢慢的捡起来，所以准备日更一道算法题目，难度自然是由简入难，所以同学们可以每天都来看看小编的更新。
- 日更时间定在每晚20:00，希望大家多多关注啦。
- 昨天就欠更了，简直就是打脸。过完年刚开工，比较忙，今天更新两道，晚上还会更新一道!!!!!
寻找最长回文子串
给定一个字符串小号，发现最长的回文子小号。您可以假设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; } } }
最后说两句
- 所有的题目都有很多种解法，我的一定不是最好的，甚至可以说是比较低端的解法，希望大牛们多多指教！！！
- 如果朋友们对算法、编程有很大兴趣的话，可以私信我，大家一同探讨；相互学习、共同进步。
- 朋友们如果对这道题目有更好的解法，希望可以在评论中指出，让大家一起讨论学习。
- 最后感谢大家的阅读以及关注，谢谢大家！！！
