LeetCode problem 20: Valid parentheses

1. Topic description

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

A valid string must meet the following requirements:

1. The left parentheses must be closed with the same type of the right parentheses. 2. The left parentheses must be closed in the correct order.

• Note: Null characters are also valid characters.

Example:

Input:'()'Output: trueCopy the code

Input:'([{}])'Output: trueCopy the code

Input:'{}])'Output:false
Copy the code

Input:'(/)'Output:false
Copy the code

Input:'(" {()})"Output:false
Copy the code

2

Given a string of parentheses, you are asked to determine whether the parentheses in the string are closed in the same order and in the correct order. We can split the string into two parts, one for the left parentheses and one for the right parentheses. First, let’s analyze the special case. One, it must be true if the string is empty and two, it must be false if the string is asymmetric and then we’re going to figure out how to match these parentheses in the string and that’s where we’re going to use our stack. A stack is a special string whose elements are “in last out”. To make it easier to understand, take a look at the figure below

• Implementation process:

1. Initialize a stack. 2. Use the for loop to loop through the string into the new array, and find the character in the open parenthesis and put it on the stack. If there is no match, return false. If there is no match, return false. When a string like ‘{}])’ is looped once, we notice that the second loop has no elements left in the stack, and the closing bracket still has elements. What should we do? So we should add false 2 if the stack length does not exist. When the parentheses inside the string match exactly, like ‘([{}])’ when the loop ends, procedure 3 is not executed and should return true so we return outside the loop! The stack length. ! Zero equals one, true

3. Code implementation

Due to my limited ability, ONLY JavaScript language code is provided for the time being. As long as you understand the idea of this algorithm, you can also implement it in other languages, which is also an exercise in personal coding ability.

/ * * *@author My name is strong I don't cry *@param {string} s
 * @return {boolean}* /

const leftToRight = {
    "(":")"."{":"}"."[":"]"
}

 var isValid = function(s) {
    if(! s) {return true
    }
    // Initialize a stack
    const stack = []
    const len = s.length
    for (let i = 0; i < len ; i++) {// when an open parenthesis is encountered
      // Otherwise, the stack element is taken out and compared
      const ch = s[i]
      if (ch == "(" || "{" || "["){
         stack.push(leftToRight[ch])
      }else {
        if(! stack.length || stack.pop() ! == ch) {return false}}}return! stack.length };Copy the code

4. To summarize

In general, when it comes to symmetry, we prefer stacks. In the early stage of brushing LeetCode, if there is no idea after thinking for a while, do not buckle, you should resolutely read others’ ideas for solving problems. After understanding, in rely on their own understanding and memory to knock again. Study = study + practice. Knowledge is learned, not popped up in your head; After you’ve learned it, you have to practice it yourself. Novices need to be brave and often learn other people’s solutions and answers, and then practice coding with understanding. As long as brush through the initial pain, the back will brush faster.

• Note: this is only my own understanding, if there is a better way, welcome to give advice.