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:Input: "babad"Output: "bab"Note: "aba" is also a valid answer.Example:Input: "cbbd"Output: "bb"

解析

• 想到了左右拓展的方法，但是开始不知道怎么处理
• 动态规划的方法

class Solution_5 {public:    // reverse(res.begin(),res.end());    // return s == string(s.rbegin(), s.rend());    bool isPalindrome(string s)    {        return s ==string(s.rbegin(),s.rend());    }    // 处理bb和aba的情况    string expandstring(const string s,int l,int r)    {        while(l >= 0&&r
    
     longestr.size())            {                longestr = expand;            }            string expand2 = expandstring(s,i,i+1);            if (expand2.length()>longestr.length())            {                longestr = expand2;            }        }        return longestr;    }};string longestPalindromeDP(string s) {  int n = s.length();  int longestBegin = 0;  int maxLen = 1;  bool table[1000][1000] = {false};  for (int i = 0; i < n; i++) {    table[i][i] = true;  }  for (int i = 0; i < n-1; i++) {    if (s[i] == s[i+1]) {      table[i][i+1] = true;      longestBegin = i;      maxLen = 2;    }  }  for (int len = 3; len <= n; len++) {   //对每个长度拓展查看    for (int i = 0; i < n-len+1; i++) {      int j = i+len-1;      if (s[i] == s[j] && table[i+1][j-1]) {        table[i][j] = true;        longestBegin = i;        maxLen = len;      }    }  }  return s.substr(longestBegin, maxLen);}
    

题目来源