LeetCode 20. Valid Parentheses (Easy)

Stack

Given a string containing just the characters ‘(’,’)’,’{’,’}’,’[’ and ’]’,determine if the input string is valid.
An input string is valid if:

1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in correct order.

题意：判断输入是否合法，类似于代码中括号合法检测。需要满足以下的test类型。

Note that an empty string is also considered valid.
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

Solution 1:四个if (error不可行)
Solution 2:计数 (error不可行) ()()()[(])
Solution 3:Stack () ,利用栈，后进先出的特性，对需入栈的元素跟栈顶元素比较，相匹配的进行移除栈操作，最后栈为空，则合法。
题解：

class Solution {
    public boolean isValid(String s) {
    	HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        Stack stack = new Stack();
        for(int i = 0;i<s.length;i++) {
            if(map.containtsKey(s.charAt(i))){ //  end with
            	Character top = stack.empty() ? "*" : statck.pop(); //remove
            	if(top != map.get(s.charAt(i))){
                     return false;
            	}
            }else{
               	stack.push(s.charAt(i));
            }
        }
     	return stack.empty();
    }
}

LeetCode 20. Valid Parentheses (Easy)

FEATURED TAGS