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;
}
           

對這題真的是聽說很久了，雖然這是給大一新生面試的題，但是我還是到現在才真的寫出來。不過寫出來終歸還是挺開心的吧。