利用动态规划法、中心扩展法解决回文子串

本文主要是介绍利用动态规划法、中心扩展法解决回文子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

利用动态规划法、中心扩展法解决回文子串

动态规划法：1.确定dp[][]，对角线是true(因为单个字母为回文串)
2.枚举子串长度，从底至右上角填完表格
3.当Si!=Sj时，false，当Si==Sj时，当最多3个字母为true，当大于3个字母取决于S[i+1,j-1]
中心扩展法：1.边界情况为1个字母或者2个字母，扩展
2.当扩展到两边字母不一致时，停止扩展

5 最长回文子串

/*** 最长回文子串*/
public class $5 {public String longestPalindrome(String s) {int len = s.length();if (len < 2) { //注意return s;}boolean[][] dp = new boolean[len][len];//初始化，所有长度为1的子串都是回文串，斜对角线为truefor (int i = 0; i < len; i++) {dp[i][i] = true;}int maxLen = 1; //注意int begin = 0;//先枚举子串长度for (int L = 2; L <= len; L++) { //L<=len 注意//枚举左边界for (int i = 0; i < len; i++) {//确定右边界int j = L+i-1;//如果右边界越界，则退出当前循环if (j >= len) {break;}//当s的第i和第j个字母不同时，不是回文串if (s.charAt(i) != s.charAt(j)) {dp[i][j] = false;} else { //当s的第i和第j个字母相同时if (j-i<3) { //最多3个字母时，肯定是是回文串dp[i][j] = true;} else { //大于3个字母时，取决于s[i+1,j-1]是否为回文串dp[i][j] = dp[i+1][j-1];}}if (dp[i][j] && j-i+1 > maxLen) {maxLen = j-i+1;begin = i;}}}return s.substring(begin, begin+maxLen); //begin+maxLen 注意}
}

/*** 最长回文子串*/
public class $5 {//中心扩展法public String longestPalindrome2(String s) {
//        if (s == null || s.isEmpty()) {
//            return "";
//        }int start = 0;int end = 0;for (int i = 0; i < s.length(); i++) {//偶数和奇数长度的回文串是不同的情况，同时考虑int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i+1);int len = Math.max(len1, len2);//时刻保证最长的回文长度//以i为中心，扩展len的长度，若len为奇数，则i左右长度相等，若len为偶数，则i左比i右少1if (len > end - start) {start = i - (len-1)/2;end = i + len/2;}}return s.substring(start, end+1);}private int expandAroundCenter(String s, int left, int right) {//针对i不断扩展，若两边值相等，则可以继续扩展while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return right - left - 1;}
}

647 回文子串

/*** 回文子串*/
public class $647 {public int countSubstrings(String s) {int len = s.length();boolean[][] dp = new boolean[len][len];int res = 0;for (int i = 0; i < len; i++) {dp[i][i] = true;res++;}for (int l = 2; l <= len; l++) {for (int i = 0; i < len; i++) {int j =  i+l-1;if (j >= len) {break;}if (s.charAt(i) == s.charAt(j)) {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i+1][j-1];}} else {dp[i][j] = false;}if (dp[i][j]) {res++;}}}return res;}
}

/*** 回文子串*/
public class $647 {//扩展法public int countSubstrings2(String s) {int cnt = 0;for (int i = 0; i < s.length(); i++) {cnt += expand(s, i, i);cnt += expand(s, i, i+1);}return cnt;}private int expand(String s, int left, int right) {int cnt = 0;while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;cnt++;}return cnt;}
}