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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

1.递归：stack overflow

public class Solution {
        public boolean isValid(String s) {
    Map<Character, Character> m = new HashMap<Character, Character>();
    // "()" and "()[]{}"
    m.put('(', ')');
    m.put('[', ']');
    m.put('{', '}');
    boolean result = false;
    while(s!=""&&s!=null){
    for (int i = 0; i < s.length(); i++) {
        if (m.containsKey(s.charAt(i))) {
            if ((i + 1) < s.length()) {
                 s.substring(i + 1);
                 String ss=findBi(s, m.get(s.charAt(i)), m);
                if (ss == null){
                    result = false;}
                else if (ss == ""){
                    result = true;}
 
                    s=ss;
                
                break;
            } else
                return false;
        }return false;
        
    }
    }
    return result;
}
 
public String findBi(String s, Character c, Map<Character, Character> m) {
    if (s==null||s.length() == 0)
        return null;
    for (int i = 0; i < s.length(); i++) {
        Character x=s.charAt(i);
        if (x == c) {
            if (i + 1 < s.length()) {
                return s.substring(i + 1);
            } else
                return "";
        } else if (m.containsKey(x) && (i + 1) < s.length()) {
            String string = findBi(s.substring(i + 1), m.get(x), m);
              System.out.println(string+"?"+c);
            if (string ==null) {
                return null;
            } else if(string == ""){
                return "";
            }
            else{
                return findBi(string, c, m);
            }
        } else if (m.containsValue(s.charAt(i))) {
            return null;
        }
    }
    return null;
}
}

2.堆栈

public class Solution {
        public boolean isValid(String s) {
            if(s.length()%2==1) return false;
         Stack stack=new Stack<Character>();
        for(Character x:s.toCharArray()){
            if(x=='('){
                stack.push(')');
            }else if(x=='['){
                stack.push(']');
            }else if(x=='{'){
                stack.push('}');
            }else if(stack.isEmpty()||stack.pop()!=x){
                return false;
            }
        }
        return stack.isEmpty();
}
}