首页 > 代码库 > Leetcode-- Longest Palindromic Substring
Leetcode-- Longest Palindromic Substring
这道题是让求最长回文字符解法有三
1.暴力解法
时间复杂度O(n3)
代码:
class Solution { public: static bool islongestPalindrome(string temp) { int i = 0; while (i != temp.length()) { if (temp[i] != temp[temp.length() - i - 1]) { return false; } ++i; } return true; } static string longestPalindrome(string s) { string temp, save; int i = 0, j = 0; while (i != s.length()) { while (j != s.length()) { temp += s[j]; ++j; if (islongestPalindrome(temp) && temp.length() > save.length()) save = temp; if (save.length() >= (s.length() - i)) return save; } temp.clear(); j = ++i; } return save; } };
解法二
从字符中间向两边蔓延
时间复杂度o(n2)
代码:
class Solution { public: static string LongestPalindrome(string s, int left, int right) { while (left >= 0 && right < s.length() && s[left] == s[right]) { left--; right++; } left += 1; return s.substr(left, right - left); } static string longestPalindrome(string s) { if (s.length() == 1) { return s; } int left, right, maxlen = 0; string str, result; for (int i = 0; i < 2 * s.length() - 1; i++) { left = i / 2; right = i / 2; if (i % 2 == 1) { ++right; } str = LongestPalindrome(s, left, right); if (str.length() > maxlen) { result = str; maxlen = (int) str.length(); } } return result; } };
解法三
动态规划
主要是设置一个二维数组,长度均为字符串长度,然后已经检测的设置为true,这样就免去了重复检测已检测的字符
时间复杂度o(n2)
代码:
class Solution { public: static string longestPalindrome(string s) { if (s.length() == 1) return s; int maxlen = 0; string temp; bool verify[s.length()][s.length()]; memset(verify, 0, sizeof(verify)); for (int i = (int) (s.length() - 1); i >= 0; i--) for (int j = i; j < s.length(); j++) { if (s[i] == s[j] && (j - i < 2 || verify[i + 1][j - 1])) { verify[i][j] = true; if ((j - i + 1) > maxlen) { maxlen = j - i + 1; temp = s.substr(i, j - i + 1); } } } return temp; } };
还有一个算法叫做Manacher算法。可以在o(n)时间度内完成此问题,有兴趣可以看下
https://www.felix021.com/blog/read.php?2040
Leetcode-- Longest Palindromic Substring
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。