Algorithm-and-Leetcode/leetcode/20. Valid Parentheses.md at master

Question:

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
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();
    }
}