今日算法之_22_最长回文子串
前言
Github：https://github.com/HealerJean
1、最长回文子串
回文串：是指这个字符串无论从左读还是从右读，所读的顺序是一样的
给定一个字符串
s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
1.1、解题思路
首先一个字符串肯定是回文
动态规划：
dp[i][j]表示i到j是回文 ，则肯定=>
dp[i][j]=true，
dp[i][j] = d[i+1][j-1]，因为有了这个条件， 按照下面的表格来说肯定是想右斜上方推进
1、首先初始化动态数组
// 初始化数组dp （i到j为回文），将对称点设置为true 也就是只有一个字符的情况
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
2、从第二列开始也就是j=1,i=0开始，然后接着j向后移动一列，i = j -1
for (int j = 1; j < len; j++) {
for (int i = j-1; i >= 0; i--) {
if (s.charAt(i) == s.charAt(j)) {
//表格中观察如果 j-i < 2的时候dp[i + 1][j - 1] 是0，所以这里要特殊处理一下，
// j - i < 2 => aa ，这种情况
if (j - i < 2) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
//如果i和j的字符不相等，则肯定是false
} else {
dp[i][j] = 0;
}
// 只要 dp[i][j] == 1 成立，就表示子串 s[i, j] 是回文，此时记录回文长度和起始位置
if (dp[i][j] == 1) {
int curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
1.2、算法
public String longestPalindrome(String s) {
int len = s.length();
//只有一个字符的时候，或者是空字符串
if (len < 2) {
return s;
}
// 初始化数组dp （i到j为回文），将对称点设置为true 也就是只有一个字符的情况
int[][] dp = new int[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
int maxLen = 1;
int start = 0;
for (int j = 1; j < len; j++) {
for (int i = j-1; i >= 0; i--) {
if (s.charAt(i) == s.charAt(j)) {
//如果字符串是 ab 或者 a ，aba ，则肯定是回文，否则如果i和j所在字符串相等的话
if (j - i < 3) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
//如果i和j的字符不相等，则肯定是false
} else {
dp[i][j] = 0;
}
// 只要 dp[i][j] == 1 成立，就表示子串 s[i, j] 是回文，此时记录回文长度和起始位置
if (dp[i][j] == 1) {
int curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
//包头不包尾
return s.substring(start, start + maxLen);
}
1.3、测试
@Test
public void test(){
System.out.println(longestPalindrome("banana"));
}
anana
