Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to achieve palindrome substring in C++". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope this article "how to achieve palindrome substring in C++" can help you solve the problem.

Palindromic Substrings palindrome substring

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", "aa", "aa", "aaa".

Note:

The input string length won "t exceed 1000.

This question gives us a string, so let's calculate how many palindromes there are. When the blogger saw this question, he subconsciously thought that it should be done with DP. He hummed and patched it for a long time, and finally passed it, but the DP written by the blogger is not the easiest way, it is slightly complicated, so it will not be posted here. It would be better to directly explain the solution of the great gods. In fact, this problem can also be done by recursion, and the train of thought is very simple and rough. That is, each character in the string is regarded as the position in the middle of the palindrome string, and then spread to both sides. every time two or so characters are successfully matched, the result res increases by 1, and then the next pair is compared. Note that the palindrome string has two forms: odd and even. If it is odd, then the position of I is the position of the middle character, so the left and right times are traversed from I. If it is of even length, then I is the left side of the middle two characters, and the right one is iTunes 1. In this way, you can cover all cases, and they are different palindromes. See the code below:

Solution 1:

Class Solution {public: int countSubstrings (strings) {if (s.empty ()) return 0; int n = s.size (), 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.size() && s[i] == s[j]) { --i; ++j; ++res; } }}; 在刚开始的时候博主提到了自己写的 DP 的方法比较复杂，为什么呢，因为博主的 dp[i][j] 定义的是范围 [i, j] 之间的子字符串的个数，这样其实还需要一个二维数组来记录子字符串 [i, j] 是否是回文串，那还不如直接就将 dp[i][j] 定义成子字符串 [i, j] 是否是回文串就行了，然后i从 n-1 往0遍历，j从i往 n-1 遍历，然后看 s[i] 和 s[j] 是否相等，这时候需要留意一下，有了 s[i] 和 s[j] 相等这个条件后，i和j的位置关系很重要，如果i和j相等了，则 dp[i][j] 肯定是 true；如果i和j是相邻的，那么 dp[i][j] 也是 true；如果i和j中间只有一个字符，那么 dp[i][j] 还是 true；如果中间有多余一个字符存在，则需要看 dp[i+1][j-1] 是否为 true，若为 true，那么 dp[i][j] 就是 true。赋值 dp[i][j] 后，如果其为 true，结果 res 自增1，参见代码如下： 解法二： class Solution {public: int countSubstrings(string s) { int n = s.size(), res = 0; vector dp(n, vector(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)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.