Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

I. Introduction to the topic

1

Link: LeetCode

2. The title

Given a string s, count and return the number of callback substrings in the string.

A palindrome string is a string that is read forward as well as backwards.

A substring is a sequence of consecutive characters in a string.

Substrings with different starting or ending positions are treated as different substrings, even if they are composed of the same characters.

Example 1:

Input: s = “ABC” Output: 3 Explanation: three callback substrings: “A “,” B “, “C”

Example 2:

Input: s = “aaa” output: 6:6 back to the text string: “a”, “a”, “a”, “aa”, “aa”, “aaa”

Tip: 1 <= S. length <= 1000 s Consists of lowercase English letters

Two. Concrete implementation

1. Implementation idea

Palindrome is the classic problem of the algorithm, but some of the problems are variations, the basic idea of solving the problem is the same, double loop, match the elements in the folded string one by one, if equal is palindrome, not equal to continue to match.

2. Implementation code

1) Their own way of implementation

public int countSubstrings(String s) {
    int res = 0;
    int n = s.length();
    // Boolea [I][j] represents string from I to j is not a palindrome string
    // Note that the outer loop should be written backwards and the inner loop should be written straight
    Dp [I][j] dp[I +1][j-1]
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            // (s.charat (I)== s.charat (j)
            if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true; res++; }}}return res;
}
Copy the code

2) How to realize the friend

The thought of using the center to expand, enumerate all the substring, then judging whether the substring palindrome, enumerated every possible palindrome center, and then to the left and right sides, each in two Pointers to expand, when two Pointers point to the same element is expanding, otherwise stop expanding, is to find the target palindrome returns.

3. Running result

3. Think after the question

I feel that since doing algorithm problems, I have seen this kind of similar question type is cycle, and then match. In fact, I have not paid attention to the time complexity. For example, in this problem, my friend’s approach is less than a layer of cycle, and the time complexity is certainly smaller than mine.