20. Valid Parentheses

递归解法

class Solution {
    public boolean isValid(String s) {
        if(s.length()==0)
            return true;
        if(s.length()==1)
            return false;
        boolean result = true;
        if(s.charAt(0)=='('){
            int i = 1,sum = -1; 
            for(;i<s.length();i++){
                if(s.charAt(i)=='('){
                    sum-=1;
                }else if(s.charAt(i)==')'){
                    sum+=1;
                    if(sum==0)break;
                }
            }
            if(i==s.length())
                return false;
            result = isValid(s.substring(1,i));
            if(i<s.length()-1)result=result&&isValid(s.substring(i+1,s.length()));
        }else if(s.charAt(0)=='['){
            int i = 1,sum = -1; 
            for(;i<s.length();i++){
                if(s.charAt(i)=='['){
                    sum-=1;
                }else if(s.charAt(i)==']'){
                    sum+=1;
                    if(sum==0)break;
                }
            }
            if(i==s.length())
                return false;
            result = result&&isValid(s.substring(1,i));
            if(i<s.length()-1)result=result&&isValid(s.substring(i+1,s.length()));
        }else if(s.charAt(0)=='{'){
            int i = 1,sum = -1; 
            for(;i<s.length();i++){
                if(s.charAt(i)=='{'){
                    sum-=1;
                }else if(s.charAt(i)=='}'){
                    sum+=1;
                    if(sum==0)break;
                }
            }
            if(i==s.length())
                return false;
            result = result&&isValid(s.substring(1,i));
            if(i<s.length()-1)result=result&&isValid(s.substring(i+1,s.length()));
        }else{
            return false;
        }
        return result;
    }
}

栈解法

使用栈会快很多

class Solution {
    public boolean isValid(String str) {
        Stack<Character> s = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char a = str.charAt(i);
            char b = pair(a);
            if (b == ' ') {
                //System.out.println(a +" " + b);
                if (s.size() == 0 || pair(s.pop()) != a) return false;
            } else {
                s.push(a);
            }
        }
        return s.size() == 0;
    }
    public char pair(char a) {
        switch (a) {
            case '(':
                return ')';
            case '{':
                return '}';
            case '[':
                return ']';
            default:
                return ' ';
        }
    }
}