fb phone希望印度姐姐手下留情

一个for loop是怎么解的？没想出来

这个问题很有趣，原题可以直接推导出所有可能解法，不用BFS，不用filter，O(number of solution) 。本来想写一个post但是实在太长了。

一个for loop得解。
思路，把string，分成多个section，把每个section 验证没问题再放进结果。两个buffer，一个存f final string， 一个存中间结果，一个counter用来做验证。
一般来说再最后一个section之前都是删除右括号，最后一个section删除左括号。

python:
rval = []
buf = []
counter = 0
for c in char:



洗完澡来说说，错了轻拍

补充内容 (2017-11-1 14:29):
打代码的时候不小心发布了。
一般来说括号验证是可以找到一个index，小于这个index的时候只能删除右括号，大于这个index的时候只能删除左括号。

补充内容 (2017-11-1 14:30):
找到这个index之后把字符串切分成一段段连续括号或者其他字符。然后这个问题就变成了类似取子集的问题。

Pony_s 发表于 2017-11-1 14:10
这个问题很有趣，原题可以直接推导出所有可能解法，不用BFS，不用filter，O(number of solution) 。本来想 ...

```
def solution(s):
    rval, buf = [], []
    counter = 0
    for c in s:
        if c == '(':
            buf.append(c)
            counter += 1
        elif c == ')':
            if counter == 0:
                if buf:
                    rval += buf
                    buf = []
            else:
                buf.append(c)
                counter -= 1
        else:
            buf.append(c)

    i = len(buf) - 1
    while i >= 0 and counter > 0:
        if buf[i] == '(':
            buf.pop(i)
            counter -= 1
        i -= 1
    rval += buf
    return "".join(rval)

print solution("aaa()((((a))(a)(((((a")
print solution("((((((((")
print solution("((())))))))")
print solution("aaaaa(aaa)(aaa)(((aaa)((a)))))))))")

```



补充内容 (2017-11-1 14:25):
随意测试了，可能还有错，代码垃圾轻拍

补充内容 (2017-11-1 15:02):
构建输出的读写不算，只有结尾多余的左括号会有两次操作，别的只有一次。

建一个缓存buff解决问题，遇到括号前存入缓存，遇到“(”括号就缓存入栈，遇到“)”就取出栈顶加上左右括号然后更新缓存，最后拼接在一起就好了
   
def removeInvalidParentheses(self, s):
        a = []
        cnt = 0
        buf = ""
        for c in s:
            if c!="(" and c!=")":
                buf+=c
            if c=="(":
                if cnt>=len(a):
                    a.append(buf)
                else:
                    a[cnt] = buf
                buf = ''
                cnt += 1
            if c==")":
                if cnt != 0:
                    buf = a[cnt-1] + '('+buf+')'
                    cnt -= 1
        return ''.join(a[0:cnt]) + buf

请问楼主出结果了嘛？还有一遍的方法有没有

lz的题好难啊，我也是面这个组，hr跟我讲说一般2题，一个warm up的easy题，一个难点的。。。。你这个怎么一上来就这么难啊。lz， 你最后过了吗？

mmymichael 发表于 2017-10-31 14:21
兄弟泥面脸书还期盼拿到ez德玛？

lol ....

请问lz bfs是怎么做的啊 我只知道 2个for loop的

发个java的解法，只扫描一遍，用stack存储invalid括号的位置，最后把invalid的括号删除就可以了

public String removeInvalid(String input) {
        Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                if (stack.isEmpty() || input.charAt(stack.peek()) != '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                }
            }
        }

        StringBuilder sb = new StringBuilder(input);
        while (!stack.isEmpty()) {
            sb.deleteCharAt(stack.pop());
        }

        return sb.toString();
    }

watercup 发表于 2017-11-8 11:28
发个java的解法，只扫描一遍，用stack存储invalid括号的位置，最后把invalid的括号删除就可以了

public  ...

6666 哥们 谢谢分享。