Topic describes

Valid parentheses

Given a string containing only '(', ')', '{', '}', '[', ']', check whether the string is valid. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string. Example 1: input: "()" output: true example 2: input: "() [] {}" output: true example 3: input: "[]" output: false example 4: input: "([]" output: false example 5: input: "{[]}" output: true Source: LeetCode Link: https://leetcode-cn.com/problems/valid-parentheses Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Their thinking

Stack first, then out

  • Define a map object with the open parenthesis as key and the close parenthesis as value.
  • Make use of the principle of stack first out later; Define stack;
  • Iterate over the parenthesis string s;
    • If it is an open parenthesis, the corresponding close parenthesis in the map is pushed;
    • Otherwise, if a close parenthesis is encountered, determine whether the currently traversed close parenthesis is equal to the element at the top of the stack;
      • If not, return false;
  • At the end of traversal, check whether the stack is empty.
    • An empty stack represents valid parentheses
    • Otherwise, invalid parentheses

code

let map: any = {
    '{' : '} '.'(' : ') '.'[' : '] '
}

function isValid(s: string) :boolean {

    let stack: string[] = [];
    let top: string | undefined;

    for(let char of s){
        let value;
        if((value = map[char])){
            stack.push(value);
        }else{
            top = stack.pop();
            if(top ! == char){return false; }}}return! stack.length; }Copy the code