首页 > 代码库 > 005. Longest Palindromic Substring

005. Longest Palindromic Substring

(1)动态规划,时间复杂度O(N^2),超时

 1 string longestPalindrome(string s) 2 { 3     if (s.size() < 2) return s; 4     int max_len = 1; 5     vector<vector<int>> vec(s.size(), vector<int>(s.size(), 0)); 6     for (int i = 0; i < s.size(); ++i) vec[i][i] = 1; 7     for (int i = 0; i < static_cast<int>(s.size()) - 1; ++i) { 8         if (s[i] == s[i + 1]) vec[i][i + 1] = 2; 9     }10     for (size_t len = 3; len <= s.size(); ++len) {11         for (size_t startPos = 0; startPos < s.size() - 2; ++startPos) {12             if (startPos + len - 1 >= s.size()) continue;13             if (s[startPos] == s[startPos + len - 1] && vec[startPos + 1][startPos + len - 2]) {14                 vec[startPos][startPos + len - 1] = vec[startPos + 1][startPos + len - 2] + 2;15             }16             else {17                 vec[startPos][startPos + len - 1] = 0;18             }19         }20     }21     int left = 0, right = 0;22     for (size_t i = 0; i < s.size(); ++i) {23         for (size_t j = 0; j < s.size(); ++j) {24             if (vec[i][j] > max_len) {25                 max_len = vec[i][j];26                 left = i; right = j;27             }28         }29     }30     return s.substr(left, right - left + 1);31 }

 

(2)以当前点为中心点,枚举所有可能的回文串,时间复杂度O(N^2),AC

 1 class Solution { 2 public: 3     string longestPalindrome(string s) { 4         int max_len = 1; 5         int left = 0, right = 0; 6         for (int i = 0; i < static_cast<int>(s.size()); ++ i) { 7             int len = 1; 8             int current = 1; 9             // odd10             while (i - len >= 0 && i + len < s.size()) {11                 if (s[i - len] == s[i + len]) {12                     current += 2; ++ len;13                 }14                 else break;15             }16             if (current > max_len) {17                 max_len = current;18                 left = i - len + 1;19                 right = i + len - 1;20             }21             // enen22             if (i + 1 < s.size() && s[i] == s[i + 1]) {23                 len = 1; current = 2;24                 while (i - len >= 0 && i + len + 1 < s.size()) {25                     if (s[i - len] == s[i + len + 1]) {26                         current += 2; ++ len;27                     }28                     else  break;29                 }30                 if (current > max_len) {31                     max_len = current;32                     left = i - len + 1;33                     right = i + len;34                 }35             }36         }37         if (max_len == 1) return s.substr(0, 1);38         else return s.substr(left, right - left + 1);39     }40 };

 

005. Longest Palindromic Substring