动态规划<1>最长回文子串(longest-palindromic-substring)

vlambda
2020-05-12

动态规划<1>最长回文子串(longest-palindromic-substring)

本节为动态规划第一题：最长回文字串(longest-palindromic-substring)，主要包括：问题描述，算法思路，复杂度分析，C++实现。

1. 问题描述

给定一个字符串s，找到s中最长的回文子串，假设s的最大长度为1000，比如：给定一个字符串s，找到s中最长的回文子串，假设s的最大长度为1000，比如：

动态规划<1>最长回文子串(longest-palindromic-substring)

2. 解法

这里以动态规划为主，介绍三种解法的思路及其编程实现，分别为暴力法、动态规划法、中心扩展算法，下面是C++代码：

#include<string>#include<vector>#include<algorithm>using namespace std;
class Solution_DP{public: //最长回文子串的三种解法 //1. 暴力法:枚举所有的子串，判断是否为回文串，保存最长的回文串 //时间复杂度O(n^3)，空间复杂度O(1). string LPS_Brute(string s) { string ans = ""; int max = 0; int len = s.length(); for (int i = 0; i < len; i++) for (int j = 1; j <= len - i; j++) { string test = s.substr(i, j); if (isP(test) && test.length() > max) { ans = s.substr(i, j); max = ans.length(); } } return ans; } bool isP(string s) { int len = s.length(); for (int i = 0; i < len / 2; i++) { if (s.at(i) != s.at(len - i - 1)) return false; } return true; } //2. 动态规划:动态规划就是将中间的计算结果暂存，减少重复计算的方法，本质上就是空间换时间 //我们用一个数组bool dp[left][right]来表示字符串从left到right这段是否为回文，若dp[left][right]=true, //要判断dp[left-1][right+1]是否为回文时，只需要判断字符串在left-1和right+1两个未知是否为相同的字符。 // 动态规划的关键：初始状态+状态转移方程： //初始状态：left=right时，dp[left][right]=true //状态转移方程：dp[left][right]=true且(left-1)和(right+1)两个未知为相同的字符时，dp[left-1][right+1]=true; //时间复杂度O(n^2)，空间复杂度O(n^2) string LPS_DP(string s){ if (s == "" || s.length() < 2) return s; int length = s.length(); int maxS = 0; int maxE = 0; int maxLen = 1; vector<vector<bool>> dp(length, vector<bool>(length)); for (int right = 1; right < length; right++) { for (int left = 0; left < right; left++) { if (s.at(left) == s.at(right) && (right - left <= 2 || dp[left + 1][right - 1])) { dp[left][right] = true; if (right - left + 1 > maxLen) { maxLen = right - left + 1; maxS = left; maxE = right; } } } } return s.substr(maxS, maxLen); } //3.中心扩散：因为回文中心的两侧互为镜像，因此可以从它的中心展开，并且只有2n-1个这样的中心 //（因为偶数长度回文子串的中心处于两字母之间） //时间复杂度O(n^2)[实际上动态规划的复杂度常系数更小],空间复杂度O(1) int EAC(string s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.at(L) == s.at(R)) { L--; R++; } return R - L - 1; } string LPS_EAC(string s) { if (s == "" || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = EAC(s, i, i); int len2 = EAC(s, i, i + 1); int len = max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } string a= s.substr(start, end - start + 1); return a; }};