2022-02-25（647. 回文子串）

本文主要是介绍2022-02-25（647. 回文子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法1：动态规划法

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。

class Solution {public int countSubstrings(String s) {// 动态规划boolean[][] dp = new boolean[s.length()][s.length()];int result = 0;for (int j = 0; j < s.length(); j++) {      //一定要把列放在外层for (int i = 0; i <= j; i++) {if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {dp[i][j] = true;result++;}}}return result;}
}

解法2：中心扩散双指针

class Solution {public int countSubstrings(String s) {int result = 0;for (int center = 0; center< 2*s.length()-1; center++) {int left=center/2;int right=left+center%2;while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){--left;++right;++result;}}return result;}
}

这篇关于2022-02-25（647. 回文子串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---