給定一個字元串 s,找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。 示例 1:輸入: "babad"輸出: "bab"註意: "aba" 也是一個有效答案。 示例 2:輸入: "cbbd"輸出: "bb" 思路一:暴力法,不說了 思路二:動態規劃 參考官方給的思路: How c ...
給定一個字元串 s,找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。
示例 1:
輸入: "babad"
輸出: "bab"
註意: "aba" 也是一個有效答案。
示例 2:
輸入: "cbbd"
輸出: "bb"
思路一:暴力法,不說了
思路二:動態規劃
參考官方給的思路:
How can we reuse a previously computed palindrome to compute a larger palindrome?
If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.
#include <iostream> #include <vector> using namespace std; string longestPalindrome(string s) { int len=s.length(); //std::cout << "len="<<len<< std::endl; int num=1;//記錄長度 int flag=0;//記錄起始位置 if(len==0) return ""; if(len==1) return s; //字元串只有一個的話返回那一個字元 vector< vector<int> > palindrome(len,vector<int>(len));//用於存儲迴文信息,全部初始為0 //int *palindrome=new int[len][len]; //首先這裡考慮如果整個字元串都沒有迴文序列,那麼就返回任意一個符號,如果有兩個挨著的字元相同,那麼就返回其中一組 for(int i=0;i<len;i++) { palindrome[i][i]=1; if((i<len-1)&&s[i]==s[i+1]) { palindrome[i][i+1]=1; num=2; flag=i; } } for (int new_num = 3; new_num <= len; new_num++)//接著從3開始設置子串的長度 { for (int j = 0; j+new_num-1 < len; j++)//枚舉子串的起始點 { if (s[j] == s[j+new_num-1] && palindrome[j+1][j+new_num-1-1]==1)//有點遞歸的感覺 { palindrome[j][j+new_num-1] = 1; flag=j; num = new_num; } } } return s.substr(flag,num); } int main() { std::string s="ac"; string ss=longestPalindrome(s); std::cout << ss << std::endl; return 0; }