给你一个字符串 s,找到 s 中最长的回文
子串
。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
法一:动态规划,首先创建一个dp二维数组,二维数组的内外层长度均为输入字符串的长度,然后dp[i][j]表示从i到j(包含两端)的串是否是回文串:
func longestPalindrome(s string) string {sz := len(s)dp := make([][]bool, sz)for i, _ := range dp {dp[i] = make([]bool, sz)dp[i][i] = true}maxPalindrome := 1maxStart := 0for len := 2; len <= sz; len++ {// 从i开始,长度为len的串for i := 0; i < sz; i++ {j := i + len - 1if j >= sz {break}if s[i] != s[j] {dp[i][j] = false// 2个或3个字符的串,如果两端相等,则它是回文串} else if j-i <= 2 {dp[i][j] = true} else {dp[i][j] = dp[i+1][j-1]}if dp[i][j] && j-i+1 > maxPalindrome {maxPalindrome = j - i + 1maxStart = i}}}return s[maxStart:maxStart+maxPalindrome]
}
C++解法:
class Solution {
public:string longestPalindrome(string s) {int size = s.size();vector<vector<bool>> temp(size, vector<bool>(size, false));for (int i = 0; i < size; ++i){temp[i][i] = true;}int curMax = 1;int resBegin = 0;for (int len = 1; len < size; ++len){for (int begin = 0; begin < size; ++begin){int end = begin + len;if (end >= size){break;}if (s[begin] == s[end]){if (end - begin <= 2) {temp[begin][end] = true;} else {temp[begin][end] = temp[begin+1][end-1];}}if (temp[begin][end]){int curLen = end - begin + 1;if (curLen > curMax){curMax = curLen;resBegin = begin;}}}}return s.substr(resBegin, curMax);}
};
如果输入字符串的长度为n,此算法时间复杂度为O(n 2 ^2 2),空间复杂度为O(n 2 ^2 2)。
法二:我们可以遍历s,每遍历到一个字符,就看以这个字符为中心的回文子串长度。由于回文子串的长度可能是奇数,也可能是偶数,因此我们遍历到一个字符时,先仅以这一个字符为中心找回文子串,然后再以这个字符和它后面的一个字符为中心找回文子串,这样可以兼顾奇数和偶数长度的回文子串:
func longestPalindrome(s string) string {curMax := 1curMaxBegin := 0for i, _ := range s {max1 := getCurPalindrome(s, i - 1, i + 1)len1 := max1 * 2 + 1max2 := getCurPalindrome(s, i, i + 1)len2 := max2 * 2lenMax := max(len1, len2)if lenMax > curMax {curMax = lenMaxcurMaxBegin = i - int((lenMax - 1) / 2)}}return s[curMaxBegin : curMaxBegin + curMax]
}func getCurPalindrome(s string, left, right int) int {leftLimit := 0rightLimit := len(s) - 1len := 0for left >= leftLimit && right <= rightLimit && s[left] == s[right] {left--;right++;len++;}return len;
}
C++实现:
class Solution {
public:string longestPalindrome(string s) {int curMax = 1;int curMaxBegin = 0;for (int i = 0; i < s.size(); ++i) {int max1 = getCurPalindrome(s, i - 1, i + 1);int len1 = max1 * 2 + 1;int max2 = getCurPalindrome(s, i, i + 1);int len2 = max2 * 2;int maxLen = max(len1, len2);if (maxLen > curMax) {curMax = maxLen;curMaxBegin = i - int((maxLen - 1) >> 1);}}return s.substr(curMaxBegin, curMax);}private:int getCurPalindrome(string &s, int left, int right) {int leftLimit = 0;int rightLimit = s.size() - 1;int len = 0;while (left >= leftLimit && right <= rightLimit && s[left] == s[right]) {--left;++right;++len;}return len;}
};
如果输入字符串的长度为n,此算法时间复杂度为O(n 2 ^2 2),空间复杂度为O(1)。
法三:如果当前有回文串abacaba,那么我们称该回文串的臂长为3,当我们遍历到第二个b时,由于我们知道前面的aba也是回文串,因此我们可以直接跳过第二个b两边的a。但如何处理偶数长度的串呢,可以给串中每个字符两边都加上#,这样不管串的长度是偶数还是奇数,最终都变为奇数长度,这里插入的字符不一定需要是原串中没有出现过的字符,因为当我们以一个字符为中心,比较其两边对应的字符时,后插入的字符和原字符不会被相互比较,比如#a#,它以a为中心,会比较两个插入的#;又比如a#a,它以#为中心,会比较两个原串中的a:
class Solution {
public:string longestPalindrome(string s) {string tmpS = "#";for (char c : s) {tmpS += c;tmpS += '#';}s = tmpS;vector<int> armLen;armLen.resize(s.size());int right = -1;int j = -1;int resMid = 1;int resArm = 0;for (int i = 0; i < s.size(); ++i) {if (right <= i) {armLen[i] = getCurPalindrome(s, i, i);}else {int iSymmetry = 2 * j - i;int iSymArmLen = armLen[iSymmetry];int skipLen = min(iSymArmLen, right - i);armLen[i] = getCurPalindrome(s, i - skipLen, i + skipLen);}if (armLen[i] + i > right) {right = armLen[i] + i;j = i;}if (armLen[i] > resArm) {resArm = armLen[i];resMid = i;}}string res;for (int i = resMid - resArm; i < resMid + resArm; ++i) {if (s[i] == '#') {continue;}res += s[i];}return res;}private:int getCurPalindrome(string& s, int left, int right) {while (left >= 0 && right <= s.size() - 1 && s[left] == s[right]) {--left;++right;}return (right - left) / 2 - 1;}
};
Go解法:
func longestPalindrome(s string) string {var builder strings.Builderfor i := 0; i < len(s); i++ {builder.WriteByte('-')builder.WriteString(s[i : i+1])}builder.WriteByte('-')s = builder.String()var armLenArr []intj := -1resMid := 0resArmLen := 0right := -1for i := 0; i < len(s); i++ {if i >= right {armLenArr = append(armLenArr, getCurArmLen(s, i, i))} else {iSymmetry := j*2 - iskip := min(right-i, armLenArr[iSymmetry])armLenArr = append(armLenArr, getCurArmLen(s, i-skip, i+skip))}if i+armLenArr[i] > right {right = i + armLenArr[i]j = i}if armLenArr[i] > resArmLen {resArmLen = armLenArr[i]resMid = i}}builder.Reset()for i := resMid - resArmLen; i <= resMid+resArmLen; i++ {if s[i] != '-' {builder.WriteByte(s[i])}}return builder.String()
}func getCurArmLen(s string, left, right int) int {for left >= 0 && right <= len(s)-1 && s[left] == s[right] {left--right++}return (right - left - 2) / 2
}
如果输入字符串的长度为n,此算法时间复杂度为O(n);要么从当前遍历的位置向后;空间复杂度为O(n)。