括号匹配(DFS/BFS)(leetcode20,301)

20. Valid Parentheses

Given a string s 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

三种括号，使用栈来操作。如果只是同一种括号，使用一个计数器即可。

class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        if (chars.length%2==1){
            return false;
        }
        for (char aChar : chars) {
            // 如果是右括号，则进入对比模式
            if(!map.containsKey(aChar)){
                if(stack.isEmpty()){
                    return false;
                }
                Character peek = stack.peek();
                if(aChar==map.get(peek)){
                    stack.pop();
                }else{
                    return false;
                }
            }else{
                //否则推入栈
                stack.push(aChar);
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

301. Remove Invalid Parentheses

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

BFS、DFS都可以，

class Solution {
    private List<String> ans = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        dfs(s,0,0,'(',')');
        return ans;
    }
    public void dfs(String s, int iStart, int jStart, char openParenthsis,char closeParenthsis){
        //dfs每次遇到
        for (int i = iStart,count =0; i < s.length(); i++) {
            if(s.charAt(i)==openParenthsis) count++;
            if(s.charAt(i)==closeParenthsis) count--;
            //if count >=0, we have not yet encounter invalid closed parenthsis.
            if (count>=0)   continue;
            for (int j = jStart; j <= i; j++) {
                if(s.charAt(j)==closeParenthsis&&(j==jStart||s.charAt(j-1)!=closeParenthsis)){
                    dfs(s.substring(0,j)+s.substring(j+1),i,j,openParenthsis,closeParenthsis);
                }
            }
            return;
        }
        String reversed = new StringBuilder(s).reverse().toString();
        if(openParenthsis=='('){
            dfs(reversed,0,0,')','(');
        }else {
            ans.add(reversed);
        }
    }
}