问题一:求一个字符串的最大回文字符串长度;
1)思路:动态规划;
2)具体描述:设立一个长度len为字符串str,用一个dp[len][len]的二维数组来表示字符串i-j下标所构成的子串的长度,经过循环计算之后我们返回最大回文子串的长度即可,即返回dp[0][len-1];
3)dp数组的具体实现:根据动态规划自底向上的思想,从回文子串到求出整个最长回文字符串,首先从str的结尾开始遍历到str 的头部,同时每一次记录dp的初始值;如果str[i]==str[j],说明i-j为回文字符串,此时应该更新dp[i][j]的值;如果str[i]≠str[j],应该判断dp[i+1][j]和dp[i][j-1]的大小,取出其中max作为最大长度更新dp[i][j]的值
4)代码实现
1 static int longestPalindrome1(String str) { 2 int len = str.length(); 3 for (int i = len - 1; i >= 0; i--) { 4 dp[i][i] = 1; 5 for (int j = i+1; j < len; j++) { 6 if(str.charAt(i) == str.charAt(j)) { 7 dp[i][j] = dp[i + 1][j - 1] +2; 8 } else { 9 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); 10 } 11 } 12 } 13 return dp[0][len-1]; 14 }
5)测试结果:测试字符串12ABCBDABADBCBA34的最大回文串,我们可以看出最大回文串为ABCBDABADBCBAB,长度为13
问题二:将上述问题修改为输出最长回文子串
1)我们知道,动态规划最优解的子问题同样也是最优解,即最长回文字符串的子串也是回文串,假设p[i][j]是回文字符串,那么p[i+1][j-1]也是回文字符串,这样最长回文字符串就能够分解成为一系列子问题来求解。
2)代码实现
1 static String longestPalindrome2(String str) { 2 int len = str.length(); 3 int maxlen = 0, start = 0; 4 for (int i = 0; i < str.length(); i++) { 5 dp[i][i] = 1; 6 if(i < len -1 && str.charAt(i) == str.charAt(i+1)) { 7 dp[i][i+1] = 1; 8 start = i; 9 maxlen = 2; 10 } 11 } 12 13 for (int i = 3; i < str.length(); i++) { //分析整个串长度 14 for (int j = 0; j < len - i; j++) { //子串其实地址 15 int m = i+j - 1; //子串结束地址 16 if(dp[j+1][i-1] == 1 && str.charAt(i) == str.charAt(j)) { 17 dp[j][i] = 1; 18 maxlen = i; 19 start = j; 20 } 21 } 22 } 23 return str.substring(start,start+maxlen-1); 24 }
2)测试输入:同样是将上述测试用例,测试字符串12ABCBDABADBCBA34的最大回文串,我们可以看出最大回文串为ABCBDABADBCBAB