找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 278|回复: 3
收起左侧

[刷题记录板] 301. Remove Invalid Parentheses

[复制链接]

23

主题

0

精华

28

积分

新米人

Rank: 1

积分
28
发表于 11-29-2016 05:37 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
  1.     public List<String> removeInvalidParentheses(String s) {
  2.         char[] charArray = s.toCharArray();
  3.         int left=0;
  4.         int right=0;
  5.         for (int i=0;i<charArray.length;i++){
  6.             if (charArray【i】=='('){
  7.                 left++;
  8.             }
  9.             else if (charArray【i】==')'){
  10.                 if (left==0){
  11.                     right++;
  12.                 }
  13.                 else
  14.                     left--;
  15.             }
  16.         }
  17.       
  18.         HashSet<String> set = new HashSet<>();
  19.         
  20.         dfs(s.toCharArray(),0,new StringBuilder(),set,left,right,0 );
  21.          List<String> list = new LinkedList<>(set);
  22.         return list;
  23.     }
  24.    
  25.     public void dfs(char[] charArray,int index, StringBuilder res, HashSet<String> set, int left, int right, int open ){
  26.         if (left<0 || right<0 || open<0 ) return ;
  27.         if (index==charArray.length){
  28.             if (left==0 && right==0 && open==0)
  29.                 set.add(res.toString());
  30.             return;
  31.         }
  32.         
  33.         int len = res.length();
  34.         if (charArray[index]=='('){
  35.             dfs(charArray,index+1,res,set,left-1,right,open );
  36.             res.append(charArray[index]);
  37.             dfs(charArray,index+1,res,set,left,right,open+1);
  38.         }
  39.         else if (charArray[index]==')'){
  40.             dfs(charArray,index+1,res,set,left,right-1,open);
  41.             res.append(charArray[index]);
  42.             dfs(charArray,index+1,res,set,left,right,open-1);
  43.         }
  44.         else{
  45.             res.append(charArray[index]);
  46.             dfs(charArray,index+1,res,set,left,right,open);
  47.         }
  48.         res.setLength(len);
  49.         
  50.     }
复制代码

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 11-29-2016 05:38 AM | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 12-1-2016 02:54 AM 来自美国米群网手机版 | 显示全部楼层
感谢taoqi610分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表