20. 有效的括号🔖栈

• https://leetcode-cn.com/problems/valid-parentheses/

问题思路

将所有的左半边括号push到栈内，然后遇到右半边括号，就将其与栈顶元素匹配测试，若能匹配成功则继续匹配，反之输出false。

在这之间注意比较当栈内没有元素了，而字符串还有待匹配的字符，输出false，当栈内还有元素，外面与之匹配测试的右半边括号，也输出false。

ts实现

function isValid(s: string): boolean {
  let stack: Array<string> = []
  for (let i of s) {
    if (['(', '[', '{'].includes(i)) {
      stack.push(i)
    } else {
      switch (i) {
        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
}

之前的java代码实现

栈实现

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

    int len = s.length();
    for (int i=0;i&lt;len;i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char left = stack.pop();
            if (left == '(' &amp;&amp; c !=')') return false;
            if (left == '[' &amp;&amp; c !=']') return false;
            if (left == '{' &amp;&amp; c !='}') return false;
        }
    }
    return stack.isEmpty();
}

}

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i< s.length();i++){
            if (s.charAt(0) == ')' || s.charAt(0) == ']' || s.charAt(0) == '}'){
                return false;
            }
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                stack.push(s.charAt(i));
            }
            if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}'){
                if (s.charAt(i) == ')'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '(')
                        return false;

                }
                if (s.charAt(i) == ']'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '[')
                        return false;

                }
                if (s.charAt(i) == '}'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '{')
                        return false;

                }
            }
        }
        if (stack.isEmpty() == true){
            return true;
        } else {
            return false;
        }

    }
}

HashMap实现

class Solution {
    private static HashMap<Character, Character> map = new HashMap<>();
    static {
        // key - value
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
    }
    
public boolean isValid(String s) {
    Stack&lt;Character&gt; stack = new Stack&lt;&gt;();
    
    int len = s.length();
    for (int i = 0; i &lt; len; i++) {
        char c = s.charAt(i);
        if (map.containsKey(c)) { // 左括号
            stack.push(c);
        } else { // 右括号
            if (stack.isEmpty()) return false;
            
            if (c != map.get(stack.pop())) return false;
        }
    }
    return stack.isEmpty();
}

}