[数据结构与算法]10月27号，比较有趣的dfs题目+stack，301. 删除无效的括号 Java Array、List、Set互相转化

301. 删除无效的括号
     有趣的困难题，难点在于题目的理解，为了加深记忆，所以用python 和 JAVA写了两遍，其实也可用用记忆化提升速度
     中间关于java中的转换有点忘记了，特地记录一下：
     Java Array、List、Set互相转化

class Solution {
    private Set<String> res = new HashSet<>();
    String s;
    public List<String> removeInvalidParentheses(String _s) {
        s = _s;
        int leftRemove =0, rightRemove =0,stack=0;
        for (char c : s.toCharArray()){
            if (c == '(') leftRemove++;
            else if (c==')'){
                if (leftRemove==0) rightRemove++;
                else leftRemove--;
            }
        }
        dfs(0,"",leftRemove,rightRemove,stack);
        return new ArrayList<>(res);
    }
    private void dfs(int idx,String curStr, int left, int right,int stack){
        if (stack<0 || left<0 || right<0|| s.length()-idx<left+right) return;
        if (left==0 && right==0 && stack==0 && idx==s.length()){
            res.add(curStr);
            return;
        }
        char x = s.charAt(idx);
        if (x=='('){
            dfs(idx+1,curStr,left-1,right,stack);
            dfs(idx+1,curStr+'(',left,right,stack+1);
        }
        else if (x==')'){
            dfs(idx+1,curStr,left,right-1,stack);
            dfs(idx+1,curStr+')',left,right,stack-1);
        }
        else {
            dfs(idx+1,curStr+x,left,right,stack);
        }
    }
}

python版本

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        cnt = 0
        stack=[]
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i]==')':
                if not stack:
                    cnt+=1
                else:
                    stack.pop()
        newli=[]
        leftcnt = len(stack)
        newli=list(s)
        res=set()
        def dfs(li,curs,lcnt,cnt,stack):
            if stack<0 or lcnt<0 or cnt<0 or len(li)<lcnt+cnt: return
            if cnt ==0 and lcnt==0 and stack==0 and not li:
                res.add(curs)
                return 
            if not li: return 
            x = li[0]
            if x =='(':
                dfs(li[1:],curs,lcnt-1,cnt,stack)
                dfs(li[1:],curs+'(',lcnt,cnt,stack+1)
            elif x!=')':
                dfs(li[1:],curs+x,lcnt,cnt,stack)
            else:
                dfs(li[1:],curs,lcnt,cnt-1,stack)
                dfs(li[1:],curs+')',lcnt,cnt,stack-1)
        dfs(newli,'',leftcnt,cnt,0)
        return list(res) if res else ['']