First, understand the topic

Attach the link to the original problem: Leetcode 20. Valid parentheses

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

  • An open parenthesis must be closed with a close parenthesis of the same type.
  • The left parentheses must be closed in the correct order.

Ii. Solution analysis

In fact, this problem will use two knowledge points to solve, one is the stack, one is the dictionary. So let’s look at the steps to solve the problem, as follows:

  • First check whether the number of strings is even, if not, directly return;
  • Create a dictionary that maps the three parentheses;
  • Iterate over the string.

Three, code implementation

Based on the above solution, we will use JS to implement this problem. The specific implementation code is as follows:

let isValid = function(s){
    // 1. Check whether the number of strings is even
    if(s.length % 2= = =1) {return false;
    }
​
    // create an empty stack
    const stack = [];
    // 3. Create a dictionary and map the three corresponding brackets into it
    const map = new Map(a); map.set('('.') ');
    map.set('{'.'} ');
    map.set('['.'] ');
​
    // 4. Loop through each parenthesis character in the string
    for(let i = 0; i < s.length; i++){
        // 5. Define a variable c to store the contents of each character
        const c = s[i];
        // 6. Check whether the current parenthesis is an open parenthesis, if so, throw one of them onto the stack
        if(map.has(c)){
            stack.push(c);
        }
        // 7. If the character traversed is not an open parenthesis
        else{
            // 8. Get the value of the last bracket in the stack
            const t = stack[stack.length - 1];
            // 9. Use the get method to correspond to the closing parenthesis corresponding to the last parenthesis on the stack.
            // Check if it is equal to the value currently traversed.
            // If it is equal, the last pair is successful and the last value is popped from the stack
            if(map.get(t) === c){
                stack.pop();
            }
            // 10. If it is not equal, it is not a valid parenthesis and returns false
            else{
                return false; }}}// 11. Valid parentheses are valid only when all matches are completed and the stack is empty
    return stack.length === 0;
}
​
console.log(isValid('[{} ()]')); // true
console.log(isValid('[} {)')); // false
Copy the code

The above is the solution of valid parentheses. I wonder if it is helpful to my friends.

We’ll see you next time at 👋👋👋