LeetCode 5. 最长回文子串

Scroll Down

题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:

输入: "cbbd"
输出: "bb"

题解

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size(), maxLength = 0, start = 0;
		vector<vector<bool>> dp(n, vector<bool>(n, false));
		string ans;
		for (int j = 0; j < n; j++) {
			for (int i = 0; i <= j; i++) {
				if (i == j) dp[i][j] = true;
				else if (j - i == 1 && s[j] == s[i]) dp[i][j] = true;
				else if (j - i > 1 && s[j] == s[i]) dp[i][j] = dp[i + 1][j - 1];
				else;
				if (dp[i][j] == true && j - i + 1 > maxLength) {
					start = i;
					maxLength = j - i + 1;
				}
			}
		}
		return s.substr(start, maxLength);
	}
};