Jst Brush LeetCode--string class problem-solving skills

Prologue

We put strings, arrays, regularization, sorting, and recursion into simple algorithms. In the next series, I will introduce them one by one in a series of articles.

string

flip words in a string

Given a string, you need to reverse the order of the characters of each word in the string, while still preserving the spaces and the initial order of the words.

Example 1:
enter: "Let's take LeetCode contest"
output: "s'teL ekat edoCteeL tsetnoc"
Note: In a string, each word is separated by a single space, and there won't be any extra spaces in the string.

Source: Leetcode ( LeetCode)
Link: https://leetcode-cn.com/problems/reverse-words-in-a-string-iii
copy

Problem-solving idea: To ensure the initial order of words and spaces; a) ensure that the order of words cannot be changed; b) ensure the reversal of words.

Step 1: Separate the sentences first, then insert them into the array after the division. The order of the array is the order of the words.

Step 2: Then reverse each word of the array.

/** * @param {string} s
 * @return {string} */
var reverseWords = function(s) {
    let arr = s.split(' ')
    let result = arr.map(item=>{
        return item.split('').reverse().join('')
    })
   return  result.join(' ')
};
copy

The code is not concise enough, so do the following.

var reverseWords = function(s) {
   return  s.split(' ').map(item => item.split('').reverse().join('')
   ).join(' ')
};
copy

You can also replace the space with a regular expression, \s means a space. Here pay attention to mastering the two usages of split.

var reverseWords = function(s) {
   return  s.split(/\s/g).map(item => item.split('').reverse().join('')
   ).join(' ')
};
copy

You can also write like this. The regular expression /\w'+/g means to recognize a word, brackets indicate optional items, w means characters, \w' indicates optional characters and ', more than one element, followed by a + sign.

Note: This is not a good solution. If the word contains commas, parentheses, etc., the end of the regular expression will be matched, and the output answer will be unsatisfactory.

var reverseWords = function(s) {
   return  s.match(/[\w']+/g).map(item => item.split('').reverse().join('')
   ).join(' ')
};
copy

Summary: The knowledge points involved in this question are as follows.

String.prototype.split
String.prototype.match
Array.prototype.map
Array.prototype.reverse
Array.prototype.join
copy

count binary substring

given a string s´╝îCounts non-nulls with the same number of 0s and 1s(continuous)The number of substrings, and all 0s and all 1s in these substrings are combined.  
Repeated substrings count their occurrences.

Example 1 :
enter: "00110011"
output: 6
 explain: There are 6 substrings with the same number of consecutive 1s and 0s: "0011", "01", "1100", "10", "0011" and "01".

Note that some repeating substrings count their occurrences.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2 :
enter: "10101"
output: 4
 explain: There are 4 substrings: "10", "01", "10", "01", which have the same number of consecutive 1s and 0s.
Notice:

s.length from 1 to 50,000 between.
s Contains only "0" or "1" characters.

Source: Leetcode ( LeetCode)
Link: https://leetcode-cn.com/problems/count-binary-substrings
copy

For such a difficult topic, first find out the law of input and output, and realize it.

How to find the pattern? Discover the relationship between input and output, and look for breakthrough points.

Solution one

Step 1: First display the relationship graph and find the rules in it.

  • The starting point is moving to the right again and again
  • Start searching 0011 from 0, stop after finding it, and then start searching from the next digit
  • Find a result to the next digit, and use the substring from the next digit to the last digit as the next input (new input, sub-input) = "recursive
  • Introduce a new concept: repeat the search process. Repeat the process of finding substrings: the behavior of finding substrings can be extracted as a public behavior.

Reference video: Portal

Step 2: Pseudocode implementation

  • Why i<str.length-1, because if the cursor is at the last digit i=str.length-1, it must not satisfy the non-empty (continuous) condition of 0 and 1 in the title, and only 1 digit is left
  • r=match(str.slice(i)) find substrings that meet the conditions
  • Find a substring that satisfies the condition and save the result
for i=0;i<str.length-1;i++
    r=match(str.slice(i))
    if r
        result.push(r)
copy

Step 3: Calculating substring code demonstration

Code thinking arrangement:

  • Use the for loop to pass the string from the first to the match function, and use the regular expression in the match function to get the character at the beginning of the string (or multiple 0s or multiple 1s)
  • Then use the repeat method to invert and repeat the multiple 0s or 1s obtained at the beginning using the XOR operation for the same number of times (for example: if '00' is obtained, then it will be '11' after the inversion)
  • Then create a regular expression, splicing the obtained characters and reversed characters, use the test method to compare with the incoming string, return the first string that is successfully compared, and save it in the array result
  • By analogy, after shaving the first character of the original string, call the match method again until there is only 1 character left in the original string, and return the length of the array result
/** * @param {string} str
 * @return {number} */
var countBinarySubstrings = function(str) {
    let resultArr = [];
    let match = (str) => {
        let beforeStr = str.match(/^(0+|1+)/)[0]
        let afterStr = (beforeStr[0]^1).toString().repeat(beforeStr.length)
        let reg = new RegExp(`^(${beforeStr}${afterStr})`)
        if(reg.test(str)){
            return RegExp.$1
        } else {
            return ''
        }
    }
    for(i=0;len=str.length-1,i<len;i++) {
        let subStr = match(str.slice(i));
        if(subStr) {
            resultArr.push(subStr)
        } 
    }
    return resultArr.length
};
copy

The above problem-solving method does not work for scenarios with relatively long strings, only 85 test cases can be run through, and there are still 5 test cases that cannot be run through.

Summary: The knowledge points involved in the above practice are as follows.

String.prototype.slice
String.prototype.match
Array.prototype.repeat
Array.prototype.push
RegExp
copy

Solution two

Code thinking arrangement:

  • cur and pre respectively record the number of consecutive occurrences of the current number (for example: 000 or 11) and the number of consecutive appearances of the previous number, and the result results in the number of substrings.
  • Determine whether the current number is the same as the next number. If they are the same, the number of occurrences of the current number cur will be increased by 1. different, the current number actually becomes the previous number, and the count of the current number is reset to 1.
  • If the number of occurrences of the previous number >= the number of occurrences of the next number, it must contain a substring that satisfies the condition. That is, if cur is less than or equal to pre, the condition is met.
/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    let pre = 0, cur = 1, count = 0
    for (let i = 0, len = s.length - 1; i < len; i++) {

        if (s[i] === s[i+1]) {
            cur++ 
        } else {
            pre = cur
            cur = 1
        }
        if (pre >= cur) { 
            count++
        }
    }
    return count
};
copy

Solution three

Code thinking arrangement:

Calculate the length of consecutive 0 or 1. For example "0011100001", then it is (2,3,4,1), only need to calculate the minimum value of two adjacent elements, because it is required that 0 and 1 must be continuous in the substring. ie sum(2 min 3, 3 min 4, 4 min 1)

string

Represented by the number of consecutive 0 or 1

number of substrings

00110011

2222

min(2, 2) + min(2, 2) + min(2, 2) = 6

001100

221

min(2, 2) + min(2, 1) = 3

const countBinarySubstrings = function(s) {
 let count = 0,len=s.length-1,resultArr = [];
 for (i=0;i<=len;i++) {
     count ++ ;
     if(s[i]!==s[i+1]) {
        resultArr.push(count);
        count = 0;
     } 
 }
    let sum=0;
    for(i=0,len=resultArr.length-1;i<len;i++) {
        sum += Math.min(resultArr[i],resultArr[i+1])
    }
    return sum;
}
copy

Summarize

  • Solution 1 is a very direct and violent solution, but it requires relatively high basic knowledge of ES6, using slice, match, repeat and other methods as well as regular expressions. However, because solution 1 is too simple and violent, it takes a lot of time to compare the regular expression with the original string, especially when the original string is very long, so solution 1 is not a good algorithm.
  • Solutions 2 and 3 are more in line with the problem-solving logic. At the same time, solutions 2 and 3 omit the process of comparing with the original string, so solutions 2 and 3 are far better than solution 1 in terms of time complexity.

Tags: Javascript leetcode regex

Posted by rameshfaj on Wed, 14 Dec 2022 04:41:54 +0300