“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[topic address]

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"Copy the code

Example 2:

Input: s = "aaa" output: 6:6 back to the text string: "a", "a", "a", "aa", "aa", "aaa"Copy the code

Tip:

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

Answer key 1

A double-layer loop retrieves all possible substrings to determine whether they are palindromic strings

If it is a palindrome string, the result value is res++

The code is as follows:

/** * Check whether the given string interval is a palindrome * @param {string} s * @param {number} l * @param {number} r * @return {Boolean} */ function check(s,l,r){ while(l<r){ if(s[l]! ==s[r]) return false; else l++,r-- } return true; } var countSubstrings = function(s) { const len = s.length; // Since each character can be a callback substring, initialize res to len let res = len; For (let I = 0; i<len-1; i++){ for(let j = i+1; j<len; j++){ if(check(s,i,j)) res++ } } return res; };Copy the code

After the above solution was submitted, it took about 320ms and only beat about 17% of users

Because the above problem is solved through a double-layer loop to obtain each substring, the check function in the inner layer determines whether the subcharacter is a palindrome string, and the time complexity is O(n³).

But what about optimization?

Finding all the substrings is a necessary process, which can only be order n ^ 2 time

Check whether each substring is a palindrome string, which can only be O(n) time

Thought along while did not have the train of thought, then brazenly saw the official problem solution

Answer key 2

The central extension is used to retrieve all the substrings of a text, instead of fetching all the substrings.

  1. The center position of all possible palindromes is first iterated through enumeration, and then the characters in the current left and right positions are determined to be equal
  2. If they are equal, the result value is increased by one, and the left and right Pointers continue to expand outward
  3. If not, exit the loop

The code is as follows:

var countSubstrings = function(s) { const n = s.length; let res = 0; // enumerate possible palindromes in the center, extending left and right // if equal, find new palindromes, res++ // otherwise exit this loop for (let I = 0; i < 2 * n - 1; i++) { let l = i >> 1, r = (i >> 1) + i % 2; while (l >= 0 && r < n && s[l] == s[r]) { res++,l--,r++ } } return res; };Copy the code

After the above solution was submitted, it took about 70ms, beating 90+% users

At this point we are done with the Leetcode-647-loop substring

If you have any questions or suggestions, please leave a comment!