首页 > 代码库 > leetcode第五题--Longest Palindromic Substring
leetcode第五题--Longest Palindromic Substring
Problem：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.
找出最大的回文子串，回文就是指字符串倒过来和之前的一样。例如aba 倒过来还是aba。abac中的最大回文子串就是aba。
我一开始想的是，start从第一个开始，right从后往前找，找到和start相同的字符时，判断是不是回文。是的话记录长度不再往前找，start++，依次类推。记录最长回文下标。最后返回。最后一个case提示Time limit exceede
class Solution {private: bool isPalindrome(string s){ bool flag = true; int len = s.length(); if (len < 3) return true; int left = 0, right = len - 1; while(left < right) { if (s[left] != s[right]) flag = false; left++; right--; } return flag;}public:string longestPalindrome(string s){ if (s.length() < 3) return s; int len = s.length(); int right = len - 1, longest = 0; int index[] = {0,0}; for (int i = 0; i < right - longest; i++) { for (int j = right; j > i + longest; j--) { if (s[i] == s[j] && (j - i + 1 > longest) ) { if(isPalindrome(s.substr(i, j - i + 1))) { index[0] = i; index[1] = j; longest = j - i + 1; break; } } } } return s.substr(index[0],longest);}};
考虑了下复杂的，如上的复杂的好像超过了n方，是n三方。
从中间向两边展开的方法可以实现n方。
class Solution {//从中间向两边展开 string expandAroundCenter(string s, int c1, int c2) { int l = c1, r = c2; int n = s.length(); while (l >= 0 && r <= n-1 && s[l] == s[r]) { l--; r++; } return s.substr(l+1, r-l-1); } public: string longestPalindrome(string s) { int n = s.length(); if (n < 3) return s; string longest; for (int i = 0; i < n-1; i++) { string p1 = expandAroundCenter(s, i, i); //长度为奇数的候选回文字符串 if (p1.length() > longest.length()) longest = p1; string p2 = expandAroundCenter(s, i, i+1);//长度为偶数的候选回文字符串 if (p2.length() > longest.length()) longest = p2; } return longest; }};
http://blog.csdn.net/feliciafay/article/details/16984031这位大牛详细分析了各种复杂度。包括O（n）
leetcode第五题--Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。