[线性 DP][中心扩展法]leetcode647：回文子串(medium)

回文子串(medium)"/>

[线性 DP][中心扩展法]leetcode647：回文子串(medium)

题目：

题解：

本题主要使用中心扩展法和动态规划解题，其实本题是 5. 最长回文子串 的子题，可以运用相同的方法解题。

---

• 中心扩展法：以当前点i位置向两边扩展（奇回文串）或以i、i+1位置（偶回文串）向两边扩展

---

• 动态规划：dp[i][j]表示表示s[i]至s[j]是否为回文串，是为1，不是为0。注意我们是从字符串尾部开始判断的，这样可以避免初始化问题。
• 状态转移方程：i==j,dp[i][j]=0 i!=j,dp[i][j]=(s[i]==s[j])&&(j<=i+1||dp[i+1][j-1]);

代码如下：

// 中心扩展法
class Solution {
public:// 思路：中心扩展法，枚举每个回文串中心，然后向左右两侧扩展，判断是否为回文串即可// 由于回文中心要么是一个字符（长度为奇数的回文子串），要么是两个字符（长度为偶数的回文子串），用一个变量j来枚举这两种情况即可int countSubstrings(string s) {int cnt=0,n=s.size();// 枚举每个回文中心ifor(int i=0;i<n;++i){for(int j=0;j<=1;++j)// j为0，表示中心为一个字符；j为1，表示中心为两个字符{int l=i,r=i+j;while(l>=0&&r<n&s[l]==s[r]){cnt++,l--,r++;}}}return cnt;}
};

class Solution {
public:int countSubstrings(string s) {int cnt=0;for(int i=0;i<s.size();++i){cnt++;for(int j=i+1;j<s.size();++j){if(isOK(s,i,j))cnt++;}}return cnt;}bool isOK(const string& s,int i,int j){while(i<j){if(s[i]!=s[j])return false;i++,j--;}return true;}
};