回文子串(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;}
};
更多推荐
[线性 DP][中心扩展法]leetcode647:回文子串(medium)
发布评论