网站开发测量像素工具,2021军事热点新闻,网络营销运营策划,媒体电商推荐理由#xff1a;暴力解法太 naive#xff0c;中心扩散不普适#xff0c;Manacher 就更不普适了#xff0c;是专门解这个问题的方法。而用动态规划我认为是最有用的#xff0c;可以帮助你举一反三的方法。
补充说明#xff1a;Manacher 算法有兴趣的朋友们可以了解一…推荐理由暴力解法太 naive中心扩散不普适Manacher 就更不普适了是专门解这个问题的方法。而用动态规划我认为是最有用的可以帮助你举一反三的方法。
补充说明Manacher 算法有兴趣的朋友们可以了解一下有人就借助它的第一步字符串预处理思想解决了 LeetCode 第 4 题。因此以上推荐仅代表个人观点。
解决这类 “最优子结构” 问题可以考虑使用 “动态规划”
1、定义 “状态” 2、找到 “状态转移方程”。
记号说明 下文中使用记号 s[l, r] 表示原始字符串的一个子串l、r 分别是区间的左右边界的索引值使用左闭、右闭区间表示左右边界可以取到。举个例子当 s babad 时s[0, 1] ba s[2, 4] bad。
1、定义 “状态”这里 “状态”数组是二维数组。
dp[l][r] 表示子串 s[l, r]包括区间左右端点是否构成回文串是一个二维布尔型数组。即如果子串 s[l, r] 是回文串那么 dp[l][r] true。
2、找到 “状态转移方程”。
首先我们很清楚一个事实
1、当子串只包含 11 个字符它一定是回文子串
2、当子串包含 2 个以上字符的时候如果 s[l, r] 是一个回文串例如 “abccba”那么这个回文串两边各往里面收缩一个字符如果可以的话的子串 s[l 1, r - 1] 也一定是回文串即如果 dp[l][r] true 成立一定有 dp[l 1][r - 1] true 成立。
根据这一点我们可以知道给出一个子串 s[l, r] 如果 s[l] ! s[r]那么这个子串就一定不是回文串。如果 s[l] s[r] 成立就接着判断 s[l 1] 与 s[r - 1]这很像中心扩散法的逆方法。
事实上当 s[l] s[r] 成立的时候dp[l][r] 的值由 dp[l 1][r - l] 决定这一点也不难思考当左右边界字符串相等的时候整个字符串是否是回文就完全由“原字符串去掉左右边界”的子串是否回文决定。但是这里还需要再多考虑一点点“原字符串去掉左右边界”的子串的边界情况。
1、当原字符串的元素个数为 33 个的时候如果左右边界相等那么去掉它们以后只剩下 11 个字符它一定是回文串故原字符串也一定是回文串
2、当原字符串的元素个数为 22 个的时候如果左右边界相等那么去掉它们以后只剩下 00 个字符显然原字符串也一定是回文串。
把上面两点归纳一下只要 s[l 1, r - 1] 至少包含两个元素就有必要继续做判断否则直接根据左右边界是否相等就能得到原字符串的回文性。而“s[l 1, r - 1] 至少包含两个元素”等价于 l 1 r - 1整理得 l - r -2或者 r - l 2。
综上如果一个字符串的左右边界相等以下二者之一成立即可 1、去掉左右边界以后的字符串不构成区间即“ s[l 1, r - 1] 至少包含两个元素”的反面即 l - r -2或者 r - l 2 2、去掉左右边界以后的字符串是回文串具体说它的回文性决定了原字符串的回文性。
于是整理成“状态转移方程”
dp[l, r] (s[l] s[r] and (l - r -2 or dp[l 1, r - 1])) 或者
dp[l, r] (s[l] s[r] and (r - l 2 or dp[l 1, r - 1])) 编码实现细节因为要构成子串 l 一定小于等于 r 我们只关心 “状态”数组“上三角”的那部分取值。理解上面的“状态转移方程”中的 (r - l 2 or dp[l 1, r - 1]) 这部分是关键因为 or 是短路运算因此如果收缩以后不构成区间那么就没有必要看继续 dp[l 1, r - 1] 的取值。
读者可以思考一下为什么在动态规划的算法中不用考虑回文串长度的奇偶性呢。想一想答案就在状态转移方程里面。
具体编码细节在代码的注释中已经体现。 class Solution {
public:string longestPalindrome(string s) {if (s.size() 2) return s;int n s.size(), maxLen 0, start 0;for (int i 0; i n - 1; i) {searchPalindrome(s, i, i, start, maxLen);searchPalindrome(s, i, i 1, start, maxLen);}return s.substr(start, maxLen);}void searchPalindrome(string s, int left, int right, int start, int maxLen) {while (left 0 right s.size() s[left] s[right]) {--left; right;}if (maxLen right - left - 1) {start left 1;maxLen right - left - 1;}}
};
