This article is participating in the nuggets team online activity, click to see the details

I. Title Description:

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.

Example 1:

Input: s = “()” output: true

Example 2:

Input: s = “()[]{}” Output: true

Example 3:

Input: s = “(]” Output: false

Tip:

1 <= s.length <= 10^4 s consists only of parentheses ‘()[]{}’

Ii. Analysis of Ideas:

The problem is simple enough to solve with a stack. According to the prompt, the string length is greater than or equal to 1, so the case of 0 can be ignored.

  • Consider the three cases ‘(‘, ‘[‘, ‘{‘), which should be pushed when the requirements are met;
  • ‘)’, ‘}’, and ‘]’ should be checked to see if the top of the stack matches the closed three characters.
    • Matching. For example, if the top of the stack is ‘(‘, the current character is ‘)’, the ‘(‘ should be pushed off the stack
    • Don’t match. Directly does not meet the requirements

Example:

s = “{[]}”

Finally, a return judgment is made based on whether the stack is empty. Return false if the match condition is not met.

Iii. AC Code:

function isValid(s: string) :boolean {
  let stack = [];
  stack[0] = s[0];
  for (let i = 1; i < s.length; i++) {
    switch (s[i]) {
      case "(":
        stack.push("(");
        break;
      case "[":
        stack.push("[");
        break;
      case "{":
        stack.push("{");
        break;
      case ")":
        if (stack[stack.length - 1= = ="(") {
          stack.pop();
        } else {
          return false;
        }
        break;
      case "]":
        if (stack[stack.length - 1= = ="[") {
          stack.pop();
        } else {
          return false;
        }
        break;
      case "}":
        if (stack[stack.length - 1= = ="{") {
          stack.pop();
        } else {
          return false;
        }
        break; }}return stack.length ? false : true;
};
Copy the code

Iv. Summary:

Using the stack to solve the string matching problem is only one solution. You can also use the key and value of the object to solve the problem.