首页 > 其他 > 详细

LeetCode "Remove Invalid Parentheses"

时间:2015-11-05 07:36:25      阅读:1869      评论:0      收藏:0      [点我收藏+]

DFS with pruning. The thought flow: for each char, we have 2 choices: pick or not - then DFS.

class Solution {
  int len;
  unordered_set<string> rec;  
  vector<string> ret;
  void go(const string &s, int i, string picked, int cl, int cr)
  {
    // prune
    if(cl < cr) return;
    if((cl - cr) > s.length()) return;
    if((picked.length() + s.length() - i) < len) return;
      
    if(i == s.length())
    {
      if(cl == cr)
      {
        auto clen = picked.length();
        if(clen >= len)
        {
          if(clen > len)
          {
            len = clen;
            rec.clear();
            ret.clear();
          }
          
          if(!rec.count(picked))
          {
            rec.insert(picked);
            ret.push_back(picked);
          }      
        }
      }
      return;
    }
        
    go(s, i + 1, picked, cl, cr); // drop
    
    char c = s[i];
    int ncl = cl, ncr = cr;
    if(c == ()        ncl ++;
    else if (c == ))  ncr ++;
    go(s, i + 1, picked + c, ncl, ncr); // pick
  }
public:
    vector<string> removeInvalidParentheses(string s) {
        len = 0;
    go(s, 0, "", 0, 0);
        return ret;
    }
};

LeetCode "Remove Invalid Parentheses"

原文:http://www.cnblogs.com/tonix/p/4938097.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!