[LeetCode] 647. Palindromic Substrings Palindromic substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won't exceed 1000.
This question gives a string, let's calculate how many palindromic substrings there are. When the blogger saw this question, he subconsciously thought that he should have used DP. He wrote it for a long time and repaired it, and finally passed it. However, the DP written by the blogger is not the easiest method, it is a bit complicated, so I won't post it here. It would be better to directly explain the solutions of the masters. In fact, this question can also be done with recursion, and the idea is very simple and crude. It is to use each character in the string as the middle position of the palindrome string, and then spread to both sides. Whenever two characters are successfully matched, res will be incremented by 1, and then the next pair will be compared. Note that palindrome strings have two forms: odd and even. If they are odd-length, then the i position is the position of the character in the middle, so they traverse from i both left and right; if they are even-length, then i is the one on the left and right of the two characters, and i+1, so that all the situations can be covered, and they are different palindrome substrings, see the code as follows:
Solution 1:
class Solution {
public:
int countSubstrings(string s) {
if (()) return 0;
int n = (), res = 0;
for (int i = 0; i < n; ++i) {
helper(s, i, i, res);
helper(s, i, i + 1, res);
}
return res;
}
void helper(string s, int i, int j, int& res) {
while (i >= 0 && j < () && s[i] == s[j]) {
--i; ++j; ++res;
}
}
};
At the beginning, the blogger mentioned that the method of DP he wrote was quite complicated. Why? Because the blogger's dp[i][j] defines the number of substrings between the range [i, j]. In fact, a two-dimensional array is needed to record whether the substring [i, j] is a palindrome string. It would be better to define dp[i][j] as a palindrome string directly. Then i traverse from n-1 to 0, j traverse from i to n-1, and then see whether s[i] and s[j] are equal. At this time, you need to pay attention to the condition that s[i] and s[j] are equal, the positional relationship between i and j is very important. If i and j are equal, then dp[i][j] is definitely true; if i and j are adjacent, then dp[i][j] is also true; if there is only one character between i and j, then dp[i][j] is still true; if there is an extra character in the middle, you need to see whether dp[i+1][j-1] is true. If it is true, then dp[i][j] is true. After assigning dp[i][j], if it is true, the result res will increase by 1. See the code as follows:
Solution 2:
class Solution {
public:
int countSubstrings(string s) {
int n = (), res = 0;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j]) ++res;
}
}
return res;
}
};
This is the end of this article about C++ implementing LeetCode (647. Pastoral substring). For more related C++ implementing Pastoral substring content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!