暴力解法,判断每一种可能,我们想,是不是判断的太多了,比如已知aba是回文串,那么判断babab串时需要从头开始一步一步判断吗?答案是不需要的,我们可以利用动态规划来记录状态,并且使用状态转移方程减少不必要的判断
首先定义状态 一维数组 dp[i,j],表示从第i个到第j个字符来表示是否是回文串,然后定义状态转移方程
dp[i,j]=dp[i+1][j-1]&&str[i]==str[j]
表示判断dp[i,j] 是否回文串,首先得满足 dp[i+1][j-1] 是回文串 且 str[i]==str[j]
image.png我们模拟一下
首先
1、dp[0][0]: b==b,dp[0][0]=true;
2、dp[0][1]: b!=a,dp[0][1]=false;
3、dp[0][2]:(b==b&&dp[1][1]);
...
这时候发现 dp[1][1] 还没赋值,还没有这个状态?
而且我们发现,从头遍历的字符串都长,要想重复利用,也是重复利用从后面开头的字符串,所以状态的递推需要从后面开始
我们倒置再模拟一下
首先
dp[5][5]: d==d dp[5][5]=true;
dp[4][4]: b==b dp[4][4]=true;
dp[4][5]=(b==d)=false
dp[3][3]=true,dp[3,4]=(a==b)=false;
dp[3][5]=((a==d)&&dp[4][4])=false
...
可见,我们成功使用了之前已经判断的字符串,状态重复使用成功
不过我们使用了双层循环,时间复杂度仍然是log(n^2)
/**
* dp[i][j] 表示 从i 到j 的字符串是否是回文
* 状态转移公式 dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]
*
* @param s
* @return
*/
public String longestPalindrome(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int start = 0;
int max = 1;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
boolean sret = (s.charAt(i) == s.charAt(j));
dp[i][j] = sret;
if (i + 1 <= j - 1) {
dp[i][j] = sret && dp[i + 1][j - 1];
}
if (dp[i][j] && (j - i + 1 > max)) {
start = i;
max = j - i + 1;
}
}
}
return s.substring(start, start + max);
}
网友评论