題目來源:https://leetcode.com/problems/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, and there exists one unique longest palindromic substring.
動態規劃,類似於lcs的解法,數組flag[i][j]記錄s從i到j是不是回文
首先初始化,i>=j時,flag[i][j]=true,這是因為s[i][i]是單字符的回文,當i>j時,為true,是因為有可能出現flag[2][1]這種情況,比如bcaa,當計算s從2到3的時候,s[2]==s[3],這時就要計算s[2+1] ?= s[3-1],總的來說,當i>j時置為true,就是為了考慮j=i+1這種情況。
接著比較s[i] ?= s[j],如果成立,那麼flag[i][j] = flag[i+1][j-1],否則直接flag[i][j]=false
c++代碼:
1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 int len = s.length(), max = 1, ss = 0, tt = 0; 5 bool flag[len][len]; 6 for (int i = 0; i < len; i++) 7 for (int j = 0; j < len; j++) 8 if (i >= j) 9 flag[i][j] = true; 10 else flag[i][j] = false; 11 for (int j = 1; j < len; j++) 12 for (int i = 0; i < j; i++) 13 { 14 if (s[i] == s[j]) 15 { 16 flag[i][j] = flag[i+1][j-1]; 17 if (flag[i][j] == true && j - i + 1 > max) 18 { 19 max = j - i + 1; 20 ss = i; 21 tt = j; 22 } 23 } 24 else flag[i][j] = false; 25 } 26 return s.substr(ss, max); 27 } 28 };