leetcode第5题

5.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.

题目大意就是求出一个字符串的最大回文子串，思路借鉴了讨论区中的某位同学，就是用两个标记依次往两头延伸，如给定a，b，判断s[a-1]与s[b+1]是否相等，若相等则–a, ++b在进行判断，直到不等为止，得出maxlen=b-a+1，代码运行时间4ms。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string longestPalindrome(string s) 
{
	if (s.empty() || 1 == s.size())
		return s;
	int i, a, b, mark, sz = s.size();
	int maxlen = 1;
	for (i = 0; i < sz && 2 * (sz - i) > maxlen;)
	{
		a = b = i;
		for (; b + 1 < sz && s[b] == s[b + 1]; ++b);
		i = b + 1; //关键步骤，替代i += 1;
		for (; a > 0 && b + 1 < sz && s[a - 1] == s[b + 1]; --a, ++b);
		if (b - a + 1 > maxlen)
		{
			mark = a;
			maxlen = b - a + 1;
		}
	}
	return s.substr(mark, maxlen);
}

代码中间一步关键步骤使程序时间减少了很多，因为在b的那个循环中间，如果b有变化则代表b前面有相同的字符，此步骤跳过了那些重复的步骤，因为在相同的字符里面肯定是最大长度的一个子串，如aceeeecd,在这个步骤中，若使用i += 1;则当ab指向s[2]时，由于s中有重复e，因此b经过调整指向了最后一个e，得出最大子串ceeeec，然后i += 1;b还是指向最后一个e，这其中很多步骤都是相当在这个回文子串在找一个最大回文子串，因此不可能得出比刚才那个还要大的回文子串，故此处i = b+1;为关键步骤。