题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
tips: 回文字符串：正读反读都一样
叙事
这道题目level为中等，读第一遍我就觉得可能会很棘手，当然立刻就有一个简单的解题思路，因为知道这种解法很烂所以一直没有coding。直到有一天····
强迫症
强迫症患者根本无法继续愉快coding了。。。只好不拖延，解决这个棘手的问题····当然肯定是因为自己菜才觉得棘手···
分析
最简单能想到的解决方案就是把字符串的所有子串枚举出来，每一个都判断是否是回文字符串，然后选长度最长的回文子串。。。后来我才知道这个算法叫暴力算法···名字很酷···暴力足以解决很多问题····代码很简单
public String longestPalindrome(String s) {
if(s.isEmpty()){
return s;
}
String res=s.substring(0,1);
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String k=s.substring(i,j);
String rk=new StringBuffer(k).reverse().toString();
if(k.equals(rk)&&k.length()>res.length()){
res=k;
}
}
}
return res;
}
一段不加注释都能看得懂的代码···我们执行了一下····
完美gg
果然···暴力的leetcode都看不过去···
现有的知识和智慧已经不够用了。然后去google解法。最强的是一个叫马拉车的算法，看起来有点复杂，而且对其他算法题帮助不大，所以拖拉的楼主决定晚点再学这个马拉车。接下来就是动态规划算法。。。等我起一个title。
动态规划
为什么单独将动态规划罗列出来呢，因为这在算法问题中好像十分普遍和重要。楼主之前刷面试题，很多算法问题的answer 作者都直接甩一句动态规划···好，今天就直面曾经欠下的债。动态规划颇有点“大事化小，小事化了”的感觉。在动态规划中有三个重要的元素最优子结构，边界，状态转移公式，我们稍后结合一个例子理解一下这仨概念~
理解动态规划有一个最典型的例子：
有面值分别为1，3，5的三种硬币若干，需要凑成11元最少需要多少硬币，凑成n元最少需要多少硬币？
和往常一样我们来一起找规律：
假如：
- 凑成0元需要0个硬币 //d(0)=0
- 凑成1元需要1个1元硬币 //d(1)=d(0)+1
- 凑成2元需要2个2元硬币 //d(2)=d(1)+1
- 凑成3元需要3个1元硬币或者1个3元硬币，那么我们选择1个3元硬币 //d(3)=min{d(2)+1,d(3-3)+1}
- 凑成4元需要1个3元硬币，1个1元硬币 //d(4)=d(3)+1;
- 凑成5元需要1个3元硬币，2个1元硬币或者1个5元硬币，那么我们选择1个5元硬币 //d(5)=min{d(4)+1,d(5-5)+1}
- 。。。。
- 抽离出来d(i)=min{ d(i-1)+1,d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
这里d(i-1)+1和d(i-vj)+1是d(i)的最优子结构，d(0)=0是边界，d(i)=min{ d(i-1)+1,d(i-vj)+1 }是状态转移公式。其实我们根据边界+状态转移公式就能得到最终动态规划的结果。
上述程序的java实现
public int dp(int n) {
n++;
int min[] = new int[n];
int[] V = {1, 3, 5};
min[0]=0;
for (int i = 1; i < n; i++) {
min[i] = min[i-1]+1;
for (int j = 0; j < V.length; j++) {
if (V[j] > i) {
break;
}
if (min[i - V[j]] < min[i-1]) {
min[i] = min[i - V[j]] + 1;
}
}
}
return min[n - 1];
}
因为我也是今天才去了解动态规划，所以有可能有些理解不对表述不对的地方。欢迎指出。
关于动态规划我看了的两篇文章：
动态规划：从新手到专家
参考：程序员小灰动态规划
动态规划解决最长回文子串
我们创建一个二维数组，boolean[][]dp,其中dp[i][j]表示字符串第i到j是否为回文。那么边界值其实很清楚了，j-i=1的都为true。状态转换如何设定呢？当字符串i所在的字符等于字符串j所在的字符，并且它的内部(dp[i+1][j-1])为回文那么dp[i][j]为true。因为这样的规律，我们要保证判断dp[i][j]的时候dp[i+1][j-1]已经判断，所以我们遍历采用i降序j升序的嵌套遍历的方式
public String longestPalindrome(String s) {
if (s.isEmpty()) {
return s;
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
int left = 0;
int right = 0;
for (int i = n - 2; i >= 0; i--) {
dp[i][i] = true;
for (int j = i + 1; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3是因为aba一定是回文
if(dp[i][j]&&right-left<j-i){
left=i;
right=j;
}
}
}
return s.substring(left,right+1);
}
这次我们再运行，发现顺利通过leetcode的考验~~
测试用例：dsfsdhadhfkdsdsfsdhadhdsfsdhadhfkddsfsdhadhfkdsahfksadhdsfsdhadhfkdsahfksadhfksddsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskdfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfdsfsdhadhfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsksahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskfkdsahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhskahfksadhfksdhfusdihfksjadfhksadjkdsahfdsjkhfksdhffhiawoeuruihweiyrtiuoncsdbfzmbfkhfioaewncfhsk
结果
哈哈好不好奇特别暴力算法呀哈哈哈哈哈~~~时间复杂度和空间复杂度达到极致的算法！！
希望大家能教教我马拉车算法！！
网友评论