Problem: 5. 最长回文子串

题目描述

思路

思路1：双指针

1.我们利用双指针从中间向两边扩散来判断是否为回文串，则关键是找到以s[i]为中心的回文串；
2.我们编写一个函数string palindrome(string &s, int left, int right)用于返回以索引为i作为中心向两边的的回文子串
3.由于可能出现奇数或者偶数长度的回文串，所以我们需要在遍历时，求出**palindrome(s, i, i)与palindrome(s, i, i + 1)**的回文串，并取出其中的较大值

思路2：动态规划

1.状态定义：dp[i][j]表示s[i…j]是回文字符串（定义为bool类型若为true则表示是回文串）；
2.状态初始化：所有长度为0的均为回文串，即dp[i][i] == true;
3.状态转移:若s[i] ！= s[j],则dp[i][j] == false,若s[i] = s[j]，则dp[i][j] = dp[i + 1][j - 1]

复杂度

思路1：
时间复杂度:

$O(N^2)$;其中$N$为字符串的长度

空间复杂度:

$O(N)$

思路2：
时间复杂度:

$O(N^2)$;其中$N$为字符串的长度

空间复杂度:

$O(N^2)$

Code

思路1：

class Solution {
public:/*** Two pointer** @param s Given string* @return string*/string longestPalindrome(string s) {string res;for (int i = 0; i < s.size(); ++i) {// Longest callback substring centered on s[i] (odd)string s1 = palindrome(s, i, i);// Longest palindromic string centered on s[i] and s[i + 1] (even number)string s2 = palindrome(s, i, i + 1);res = res.size() > s1.size() ? res : s1;res = res.size() > s2.size() ? res : s2;}return res;}/*** Gets the longest palindrome string between [left,right]** @param s Given string* @param left Left pointer* @param right Right pointer* @return string*/string palindrome(string &s, int left, int right) {while (left >= 0 && right < s.size() && s.at(left) == s.at(right)) {left--;right++;}return s.substr(left + 1, right - left - 1);}
};

思路2：

class Solution {
public:/*** Dynamic programming** @param s Given string* @return string*/string longestPalindrome(string s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] Indicates whether s[i..j] is a palindrome stringvector<vector<bool>> dp(len, vector<bool>(len));for (int i = 0; i < len; ++i) {dp[i][i] = true;}for (int L = 2; L <= len; ++L) {// Initialization: All substrings of length 1 are palindromesfor (int l = 0; l < len; ++l) {// L and l can determine the right boundary, that is, r - l + 1 = Lint r = L + l - 1;// If the right boundary is out of bounds, you can exit the current loopif (r >= len) {break;}if (s.at(l) != s.at(r)) {dp[l][r] = false;} else {if (r - l < 3) {dp[l][r] = true;} else {dp[l][r] = dp[l + 1][r - 1];}}// As long as dp[i][L] == true is true, it means that// the substring s[i..L] is a palindrome,// in which case the palindrome length and starting position are recordedif (dp[l][r] && r - l + 1 >= maxLen) {maxLen = r - l + 1;begin = l;}}}return s.substr(begin, maxLen);}
};