回文子串（DP）

回文子串（DP）

文章目录

​​回文子串​​

​​1. 动态规划法​​​​2. 中心拓展​​

​​最长回文子串​​

​​1. 动态规划​​​​2. 中心扩展​​

回文子串

1. 动态规划法

首先这一题可以使用动态规划来进行解决：

这个状态转移方程是什么意思呢？

填写6x6 dp数组的顺序如下

当字串长度不超过3（j-i <= 2），如果首尾字符相等，就能确定当前字串是回文串，即图中蓝色方格填写不需要查询dp数组

而红色方格处需要查询dp数组，查询dp数组时需要查看当前方格左下角的值（左下角的数据记录了内侧子串是否是回文串），可以看到当填写红色方格时，左下角的已经填写了，可以用于查询

当我们判断字符串区间[i,j]内的子串是否是回文串时，如果两侧字符相等，我们需要判断内侧的子串是否是回文串（前面求解过，从dp数组直接查询），这样我们就能判断当前子串是否是回文串

class Solution {public: int countSubstrings(string s) { int n = s.size(); int cnt = 0; vector> dp(n, vector(n, false)); for(int j = 0; j < n; j++){ for(int i = 0; i <= j; i++){ if((s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])){ dp[i][j] = true; cnt++; } } } return cnt; }};

2. 中心拓展

中心拓展，就是挨个遍历，中心可能是1个字符也可能是2个字符

class Solution {public: int cnt = 0; // 以一个字符为中心，回文串的长度为奇数 void fun1(const string& s, int mid){ cnt++; int l = mid - 1; int r = mid + 1; while(l >= 0 && r < s.size() && s[l] == s[r]){ // 不越界和两侧字符相等的情况下，数量++ cnt++; l--; r++; } } // 以两个字符为中心，回文串的长度为偶数 void fun2(const string& s, int l, int r){ while(l >= 0 && r < s.size() && s[l] == s[r]){ cnt++; l--; r++; } } int countSubstrings(string s) { for(int i = 0; i < s.size(); i++){ fun1(s, i); fun2(s, i, i+1); } return cnt; }};

最长回文子串

1. 动态规划

思路参考上一题

class Solution {public: string longestPalindrome(string s) { int n = s.size(); vector> dp(n, vector(n, false)); int l = 0; int r = 0; for(int j = 0; j < n; j++){ for(int i = 0; i <= j; i++){ if(s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])){ dp[i][j] = true; if(j - i > r - l){ l = i; r = j; } } } } return string(s, l, r - l + 1); }};

2. 中心扩展

思路参考上一题

class Solution {public: int start = 0; int end = 0; // 以一个字符为中心，回文串的长度为奇数 void fun1(const string& s, int mid){ int l = mid - 1; int r = mid + 1; while(l >= 0 && r < s.size() && s[l] == s[r]){ // 不越界和两侧字符相等的情况下，数量++ if(r - l > end - start){ start = l; end = r; } l--; r++; } } // 以两个字符为中心，回文串的长度为偶数 void fun2(const string& s, int l, int r){ while(l >= 0 && r < s.size() && s[l] == s[r]){ if(r - l > end - start){ start = l; end = r; } l--; r++; } } string longestPalindrome(string s) { for(int i = 0; i < s.size(); i++){ fun1(s, i); fun2(s, i, i+1); } return string(s, start, end - start + 1); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。