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<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 == '(' && c !=')') return false;
                if (left == '[' && c !=']') return false;
                if (left == '{' && 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<Character> stack = new Stack<>();
		
		int len = s.length();
		for (int i = 0; i < 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();
    }
}