5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"



// 非dp方法
class Solution { public: int index = 0, maxLength = 0; string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; for (int i = 0; i < n; ++i) { update(s,i,i); update(s,i,i+1); } return s.substr(index,maxLength); } void update(string s, int i, int j) { while(i >= 0 && j < s.size() && s[i] == s[j]) { --i; ++j; } int length = j - i - 1; if (maxLength < length) { index = i + 1; maxLength = length; } } }

 

// dp 方法
class Solution { public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; vector<bool> temp(n); vector<vector<bool>> dp; dp.resize(n,temp); int index = 0, maxLength = 0; for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { dp[i][j] = ((s[i] == s[j]) && (j - i < 3 || dp[i + 1][j - 1])); if (dp[i][j] && maxLength < j - i + 1) { index = i; maxLength = j - i + 1; } } } return s.substr(index, maxLength); } };

 

上一篇:刷题5. Longest Palindromic Substring


下一篇:刷题3. Longest Substring Without Repeating Characters