leetcode刷题笔记 5.最长回文子串【中等】

动态规划

记录最长回文子串和最靠右侧的最长回文子串

string longestPalindrome(string s) {
	int n = s.size();
	int left = 0;
	string max = "";
	max.push_back(s[0]);
	for (int i = 0; i < n; i++) {
		if (left - 1 >= 0 && s[left - 1] == s[i]) {//左右同时延伸
			left = left - 1;
		}			
		else {
			int p = left, q = i;
			while (p < q) {
				if (s[p] == s[q]) {
					p++; q--;
				}
				else {
					q = i;
					if (s[p] != s[q]) {
						p++;
					}
				}
			}
			if (p == q)
				left = 2 * p - i;
			else
				left = 2 * p - i - 1;
		}
		if (i - left + 1 > max.size()) {
			max = s.substr(left, i - left + 1);
		}
	}
	return max;
}
           

对这题真的是听说很久了，虽然这是给大一新生面试的题，但是我还是到现在才真的写出来。不过写出来终归还是挺开心的吧。