T N T

美食博主

0%

#5 Longest Palindromic Substring

Posted on Edited on In

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1: 

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example2: 

1
2
Input: "cbbd"
Output: "bb"

解法一 暴力法

思想：以每一个字符为中心向两边扩散，时间复杂度O(n^2); 注意回文子串奇偶情况不同，偶数以本字符和下一个字符为中心扩散。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
		public:
		string longestPalindrome(string s) {
				if (s.size() < 2) return s;
				int n = s.size(), maxLen = 0, start = 0;
				for (int i=0; i<n-1; i++) {
						searchPalindrome(s, i, i, start, maxLen);
						searchPalindrome(s, i, i+1, start, maxLen);
				}
				return s.substr(start, maxLen);
		}

		void searchPalindrome(string s, int left, int right, int &start, int &maxLen) {
				while (left>=0 && right<size() && s[left]==s[right]) {
						--left;
						++right;
				}
				if (maxLen<right-left-1) {
						start = left +1;
						maxLen = right -left -1;
				}
		}
};

解法二 马拉车算法Manacher's Algorithm

pass