刷
July-12-2019
前面123刷逼逼一大堆什么乱七八糟的。。
暴力O(nn)
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
String res = "";
for (int i = 0; i < s.length(); i ++) {
String tempStr = getPalindrome(i, i, s);
if (tempStr.length() > res.length()) {
res = tempStr;
}
tempStr = getPalindrome(i, i + 1, s);
if (tempStr.length() > res.length()) {
res = tempStr;
}
}
return res;
}
public String getPalindrome(int l, int r, String s) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l --;
r ++;
}
return s.substring(l + 1, r);
}
}
上来就觉得是动态规划，然后惨遭打脸，动态规划不是最优解。
其实可以理解，因为动态规划里，内层循环的String长度是从大到小，一旦发现Palindrome，那么此时内层循环的最长回文数列已经确定，按理说可以break.可是，没进行判断的部分以后可能被用到，所以没法BREAK。。
public class Solution
{
public String longestPalindrome(String s)
{
if(s.length() <= 1) return s;
boolean[][] P = new boolean[s.length()][s.length()];
String res = new String();
for(int i = 0; i < s.length();i++) P[i][i] = true;
int max = 0;
for(int i = 0; i < s.length();i++)
{
for(int j = 0; j < i; j++)
{
P[j][i] = (s.charAt(j) == s.charAt(i) && (i-j <= 2 || P[j+1][i-1]));
if(P[j][i])
{
if(i-j + 1 > max)
{
max = i-j+1;
res = new String(s.substring(j,i+1));
}
}
}
}
return res;
}
}
正确的做法是backtrack. 回文判断从中间判断比较划算，因为一旦失败，就没有继续往外判断的意义了，可以back track。
所以就遍历，从遍历的位置为中心往两边判断。
需要注意，ABA ABBA这俩都算回文，第一个中心是B，第二个是BB（也可以看做是BB之间的空隙）。
所以遍历的时候，每个位置要先以当前字母为中心，再以当前字母和他右边那个为中心。。
public class Solution
{
public String longestPalindrome(String s)
{
if(s.length() <= 1) return s;
int max = 0;
String res = new String();
for(int i = 0; i < s.length();i++)
{
int L = i, R = i;
String temp = getPlength(s,L,R);
if(temp.length() > max)
{
max = temp.length();
res = new String(temp);
}
if(i != s.length() - 1)
{
L = i; R = i + 1;
temp = getPlength(s,L,R);
if(temp.length() > max)
{
max = temp.length();
res = new String(temp);
}
}
}
return res;
}
public String getPlength(String s, int L , int R)
{
while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R))
{
L--;R++;
}
return s.substring(L+1,R);
}
}
时间上确实比DP要快。
然后又打脸了，发现答案里还有个O(n)的办法。。。
上面2个都是n²：
第一个没剪枝，用动态规划保存一些数据，不用每次判断回文。
第二个剪枝，但是每次必须重新判断回文，好在是从里往外，很容易break.
O(N)的还没看。。下次刷再说吧。。
放个O（N）的传送门
（http://articles.leetcode.com/longest-palindromic-substring-part-ii）