20. Valid Parentheses

Question:

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 the correct order. 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

Thinking:

• Method1:Stack Push left side into stack and every time we get a right side, just pop the stack and check if they compairs.

	class Solution {
	    public boolean isValid(String s) {
	        Stack<Character> stack = new Stack<>();
	        Map<Character, Character> m = new HashMap<>();
	        m.put(')', '(');
	        m.put(']', '[');
	        m.put('}', '{');
	        int len = s.length();
	        for(int i = 0; i < len; i++){
	            char c = s.charAt(i);
	            if(m.values().contains(c)){
	                stack.push(c);                
	            }else{
	                if(!m.keySet().contains(c)){
	                    return false;
	                }else{
	                    if(stack.size() != 0){
	                        Character temp = stack.pop();
	                        if(temp == null || temp != m.get(c)) return false;
	                    }else   return false;
	                }
	            }
	        }
	        if(stack.size() != 0) return false;
	        return true;
	     }
	}

• Method2:String replace This method is very slow.

    class Solution {
        public boolean isValid(String s) {        
            int len = 0;
            if(s.length() == 0) return true;
            while(s.length() != len){
                len = s.length();
                s = s.replace("{}", "").replace("()", "").replace("[]", "");
            }
  
            return s.length() == 0;
         }
    }
  

二刷

使用Stack结构存储（[{，接到右侧符号则判断栈顶的元素是否与之对应，如果对应则出栈并继续，如果不对应则返回false。

遍历到字符串末尾时判断是当前栈为空，不为空的元素已经没有机会找到右侧的符号进行匹配，返回false，如果为空则说明所有的元素均被匹配了，返回true。

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

Amazon session

• Method 1: Stack

    class Solution {
        public boolean isValid(String s) {
            if(s == null || s.length() == 0) return true;
            char[] arr = s.toCharArray();
            Stack<Character> stack = new Stack<>();
            for(char c : arr){
                if(c == '[' || c == '(' || c == '{') stack.push(c);
                else{
                    if(stack.isEmpty()) return false;
                    if(c == ']'){
                        if(stack.peek() == '[')
                            stack.pop();
                        else return false;
                    }else if(c == ')'){
                        if(stack.peek() == '(')
                            stack.pop();
                        else return false;
                    }else if(c == '}'){
                        if(stack.peek() == '{')
                            stack.pop();
                        else return false;
                    }
                }
            }
            return stack.size() == 0;
        }
    }