5. Longest Palindromic Substring

Description

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

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Analysis

非常经典的一个问题,求最长回文字串。

这道题看似容易解决,似乎将字符串逆置后,和原字符串作比较,找出两者的最长公共字串即可。

但实际上此种解法只是看似可行,比如对于babad,可以用这种方法找到其最长回文字串。但如果一个较长的非回文字串出现在原字符串中,比如abcdefghg`,那么很容易就能证明,上述算法会得出一个错误的答案,所以需要换一个角度进行考虑。

那么下一个比较容易想到的方法就是暴力破解了,穷举所有字串,判断其是否是回文字符串。但这样的时间空间复杂度都相当高(O(N^3)),所以只能放弃这个方法。

考虑构成回文串的条件,如果区间(i,j)能构成回文串,那么(i+1,j-1)一定也能构成回文串。所以我们可以以一个字母为”mid”,不断向两边扩张,直到不构成回文串为止。计算回文串长度和起始位置。

待mid指针遍历过所有字母之后,通过之前维护的max_left,max_len两个变量,计算出最长回文字符串。

时间复杂度为O(N^2),空间复杂度O(1),代码耗时6ms

code

class Solution {
public:
    string longestPalindrome(string s) {
		if(s.size()<2)
			return s;
		int max_len=1,max_left=0;
		for(int mid=0;mid<s.size();){
		    int left=mid;
			int right=mid; 
			while(right<s.size()-1&&s[left]==s[left+1])	++left;
			mid=left+1;
			while(right<s.size()-1&&left>0&&s[left-1]==s[right+1]){--left; ++right;}
			int new_len=right-left+1;
			if(new_len>max_len){max_left=left; max_len=new_len;}
		}
		return s.substr(max_left,max_len);
    }
};

动态规划解法

刚才在上一种解法中,已经找到了一个串为回文串的条件。

  • dp[i][j]==true为串s[i][j]为回文
  • 将dp[i][i],dp[i][i-1]初始化为true,其余全为false(即一个或两个字母组成的字符串均认为是回文)
  • 之后穷举字串长度的值,对于其是否为回文,取决于 (s[i] == s[j] && dp[i+1][j-1] == true)

时间复杂度O(N^2),空间复杂度O(N^2)

code

/*Dynamic programming*/
class Solution {
public:
    string longestPalindrome(string s) {
		if(s.size()<2)
			return s;
		int max_len=1,max_left=0,s_len=s.size();
		bool dp[s_len][s_len]={false};
		dp[0][0]=true;
		for(int i=1;i<s_len;++i){
			dp[i][i]=true;
			dp[i][i-1]=true;
		}
		for(int len=2;len<s_len;++len){
			for(int i=0;i<=s_len-len;++i){
				if(s[i]==s[i+len-1]&&dp[i+1][i+len-2]){
					dp[i][i+len-1]=true;
					if(len>max_len){
						max_left=i;
						max_len=len;
					}
				}
			}
		}
		return s.substr(max_left,max_len);
    }
};

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017