首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。