5. Longest Palindromic Substring

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

Example 1:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”

Output: “bb”

問題：

尋找字元串裡面的最長回文子串。

啥叫回文串呢？

對于字元串s,如果它的轉置s’ 等于s本身，那麼字元串s就是回文串。

例如:s=1234,那麼s’=4321,顯然s不等于s’,于是s不是回文串。

s=abba，s’=abba，因為s==s’，于是s是個回文串。

解法：

對于一個字元串，周遊所有可能的回文串中心，從回文串中心往兩邊比對。注意處理回文串長度為偶數的問題。當回文串的長度為偶數的時候，它的對稱中心就不是整數了，例如s=eeee,s[1]與s[2]比對。

時間複雜度： O ( n 2 ) O(n^2) O(n2)

class Solution {
public:
	bool isValid(int length, int index)
	{
		return index >= 0 && index < length;
	}
	string longestPalindrome(string s) {
		int mid=0,l=s.length();
		size_t st=0, max = 1;
		for (mid = 0; mid < l; mid++)
		{
			int i;
			//奇數情況
			for (i = 1; i <l;)
			{
				if (isValid(l, mid + i) && isValid(l, mid - i) && s[mid + i] == s[mid - i])
				{
					i++;
				}
				else
				{
					break;
				}
			}
			i--;
			if ((i * 2 + 1) > max)
			{
				max = i * 2 + 1;
				st = mid - i;
			}
			//偶數情況
			for (i = 0; i < l;)
			{
				if (isValid(l, mid-i) && isValid(l, mid+i+1)&& s[mid-i] == s[mid +i+1])
				{
					i++;
				}
				else
				{
					break;
				}
			}
			i--;
			if (2 * (i + 1) > max)
			{
				max = (i+1) * 2;
				st = mid - i;
			}
		}
		return s.substr(st, max);
	}
};
           

結果：

Runtime: 20 ms, faster than 75.93% of C++ online submissions for Longest Palindromic Substring.

Memory Usage: 8.7 MB, less than 90.34% of C++ online submissions for Longest Palindromic Substring.

小小的優化一下：

這個簡單的方法其實可以再小小的優化一下，因為max儲存的是目前遇到的最長回文子串的長度，是以在判斷一個新的回文中心的時候，可以通過檢測到mid相矩max/2（或（max-1）/2）的左右兩個位置是否相等來快速把一些明顯不正确的回文中心過濾掉。

class Solution {
public:
	bool isValid(int length, int index)
	{
		return index >= 0 && index < length;
	}
	string longestPalindrome(string s) {
		int mid=0,l=s.length();
		size_t st=0, max = 1;
		for (mid = 0; mid < l; mid++)
		{
			int i;
			//奇數情況
			//可以預判斷一下!!!!!!!這裡是新增的優化政策
			if((!(isValid(l, mid + (max-1)/2) && isValid(l, mid - (max-1)/2) && s[mid + (max-1)/2] == s[mid - (max-1)/2])) && !(isValid(l, mid + max/2 + 1) && isValid(l, mid - max/2) && s[mid + max/2 + 1] == s[mid - max/2]))
			{
				continue;
			}
			for (i = 1; i <l;)
			{
				if (isValid(l, mid + i) && isValid(l, mid - i) && s[mid + i] == s[mid - i])
				{
					i++;
				}
				else
				{
					break;
				}
			}
			i--;
			if ((i * 2 + 1) > max)
			{
				max = i * 2 + 1;
				st = mid - i;
			}
			//偶數情況
			for (i = 0; i < l;)
			{
				if (isValid(l, mid-i) && isValid(l, mid+i+1)&& s[mid-i] == s[mid +i+1])
				{
					i++;
				}
				else
				{
					break;
				}
			}
			i--;
			if (2 * (i + 1) > max)
			{
				max = (i+1) * 2;
				st = mid - i;
			}
		}
		return s.substr(st, max);
	}
};
           

結果：

Runtime: 8 ms, faster than 91.01% of C++ online submissions for Longest Palindromic Substring.

Memory Usage: 8.6 MB, less than 97.93% of C++ online submissions for Longest Palindromic Substring.

整整提速了12ms!!! ，這個還是特别快的！