前言：
如今兄弟们对“最近最久算法”可能比较珍视，咱们都想要了解一些“最近最久算法”的相关文章。那么小编也在网上搜集了一些有关“最近最久算法””的相关知识，希望看官们能喜欢，大家一起来学习一下吧！先解释一下什么是回文字符串，比如说字符串“aba”，无论是从先往后读取还是从后往前读取，结果都是一样的。当给定很长的字符串时，如何快速获取到最长的回文字符串，这也是大厂比较常见的算法面试题，那么这里给出三种解法。
1.暴力穷举法思路：即遍历每种子字符串，然后判断该子字符串是否为回文(即前半部分是否等于后半部分)，时间复杂度为O(n*n*n)
暴力穷举
2.中间扩散法
从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。
1.首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
2.然后往右寻找与当前位置相同的字符，直到遇到不相等为止。
3.最后左右双向扩散，直到左和右不相等。如下图所示:
中间扩散法
3.动态规划法
一开始我刚听到动态规划这个词的时候感觉很高大上，后来经过查找资料发现其实很简单，只不是从下向上的计算，说白了就是空间换时间，把中间的计算结果暂存起来，避免重复计算；
思路：
1.我们用一个 boolean dp[i][j]表示字符串从 i 到 j 这段是否为回文。
2.试想如果dp[i][j]=true，我们要判断 dp[i-1][j+1]是否为回文。
只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符，是不是减少了很多重复计算。动态规划关键是找到初始状态和状态转移方程。
初始状态，l=r 时，此时 dp[l][r]=true。
状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。
动态规划法
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #最近最久算法 #java实现回文字符算法有哪些
