脸熟 新鲜面巾

mameko 发表于 2017-6-27 20:43
其实我才发现我的是简化版，不用输出所有删除以后合法串，输出一个就好了。用栈就能搞定...

Thanks for clarification. I think using a counter to maintain the count difference between '(' and ')' should be able to replace the stack. It's done in two passes (assuming the given string is only one char extra from valid string.)

1. string RemoveInvalidParantheses(string s) {
   
2.   int counter = 0;
   
3.   for (auto i = s.begin(); i < s.end(); ++i)
   
4.   {
   
5.     if (*i == '(') ++counter;
   
6.     else if (*i == ')' && --counter < 0)
   
7.       return s.erase(i), s;
   
8.   }
   
9. 
   
10.   counter = 0;
    
11.   for (auto i = s.end()-1; i >= s.begin(); --i)
    
12.   {
    
13.     if (*i == ')') ++counter;
    
14.     else if (*i == '(' && --counter < 0)
    
15.       return s.erase(i), s;
    
16.   }
    
17.   return s;
    
18. }
    

复制代码

f1371342385 发表于 2017-6-27 10:22
见过一个follow up，但是限制最大是两位，可以用map来存一下，解法还是一样的。但是如果你这个不知道多少位 ...

I think with unordered_map<int, char> code in general case and with maximum k digits in code, the dp equation dp[ i] will be

for (int len = 1; len <= k; ++len) {
   dp[ i] += dp[ i+len]*code.count(stoi(s.substr(i, len)));
}

and it needs k initial values to start loop.

Great，thanks