5. Longest Palindromic Substring

Question

LeetCode Problem

Given a string s, return the longest palindromic substring in s.

Constraints

• 1 <= s.length <= 1000
• s consists only of digits and English letters (both lowercase and uppercase).

Solutions

O(N^2) method

string longestPalindrome(string s) {
	int m = s.size();
	if (m < 2) return s;
	int bestLen = 1;
	int bestStart = 0;
	auto expand = [&](int left, int right) {
		while (left >= 0 && right < m && s[left] == s[right]) {
			--left;
			++right;
		}
		// now s[left+1] ~ s[right-1] is the palidrome string
		int distance = right - left - 1;
		int start = left + 1;
		if (distance > maxLen) {
			maxLen = distance;
			bestStart = start;
		}
	};
	for (int i = 0; i < m; ++i) {
		expand(i, i);
		expand(i , i + 1);
	}
	return s.substr(bestStart, bestLen);
}

Use DP

• DP 定義：
  • dp[i][j] 是字串在區間 [i, j] 時的子字串是否為palindromic
  • 其中 i 的範圍為：0 ~ m - 1, j 的範圍為i ~ m - 1
• 遞推公式：
  • case 1: if i == j => dp[i][j] = true
  • case 2: if s[i] == s[j] and j - i == 1 => dp[i][j] = true
  • case 3: if s[i] == s[j] and j - i > 1 and dp[i+1][j-1] == true => dp[i][j] = true

string longestPalindrome(string s) {
	int m = static_cast<int>(s.size());
	if (m == 0) return s;
	vector<vector<bool>> dp(m, vector<bool>(m, false));
	int maxLen = 1;
	int bestStart = 0;
	for (int i = (m-1); i >= 0; i--) {
		for (int j = i, j < m; j++) {
			if (s[i] == s[j]) {
				if (j - i <= 1) {
					dp[i][j] = true;
				} else if (dp[i+1][j-1]) {
					dp[i][j] = true;
				}
			}
			if (dp[i][j]) {
				int distance = j - i + 1;
				if (distance > maxLen) {
					maxLen = distance;
					bestStart = i;
				}
			}
		}
	}
	return s.substr(bestStart, maxLen);
}