647. Palindromic Substrings

Question

LeetCode Problem

Given a string s , return the number of palindromic substrings in it .
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:

Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

Solutions

Use DP

• DP 數組定義：dp[i][j] 為當i, j 中間字串為回文的時候，是不是一個回文串。數值定義為bool
• 遞推公式：
  • if i == j -> dp[i][j] = true -> 是回文
  • if j - i = 1 && s[i] == s[j] -> dp[i][j] = true -> 是回文
  • if j - i > 1 && s[i] == s[j] && dp[i+1][j-1] == true -> dp[i][j] = true -> 是回文

a   a   a   a   b   a   a  a   a 
^   ^            ^.   ^
i. (i+1)        (j-1) j

Time Complexity: O(N^2)
Space Complexity: O(N^2)

int countSubStrings(string s) {
	int m = static_cast<int>(s.size());
	// dp[i][j] definition
	// string between i and j (closure: [i, j]) is a palindromic string. value type if boolean. 
	// i and j both are range from 0. to m - 1
	// j >= i
	// recurrence fomula:
	// case 1: when i == j mean s[i] == s[j], true
	// case 2: when j - i == 1 and s[j] == s[j], true
	// case 3: when j - i > 1 , if dp[i+1][i-1] is true then dp[i][j] is true
	// final answer is to count how many dp[i][j] == true;
	vector<vector<bool>> dp(m, vector<bool>(m, false));
	int counts = 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] == true) dp[i][j] = true; 
			}
			if (dp[i][j] == true) {
				counts += 1;
			}
		}
	}
	return counts;
}

Use DP + expand from center

This approach reduce space complexity from O(N^2) to O(N)

bool isPalidrom(int left, int right, string &s) {
	int lp = left;
	int rp = right;
	while (left <= right) {
		if (s[left] == s[right]) {
			if (j -i <= 1) {
				return true;
			} 
		} else {
			return false;
		}
		left++;
		right--;
	}
	return true;
}
int countSubstrings(string s) {
	int m = static_cast<int>(s.size());
	for (int i = 0; i < m; ++i) {
		
	}
}