facebook最高频（就是最高的，没有之一）题目的follow up

xp1991112 发表于 2022-2-8 20:09
感觉就是stack解法的follow up？用三个stack 分别记录（，]和}的index。以小括号举个例子，如果遇到的是） ...

这个思路不行吧
如果是{[}, 这个greedy办法会把三个都delete，而最优方案是只删中间一个。
https://leetcode.com/playground/En5cpBhW

我覺得你可以看一下301? 你把其中一個字元拿掉再去做dfs and check the error number of parentheses <= current error number of parentheses，最後應該可以得到最長的字串！

leonsu7777 发表于 2022-2-8 22:10
这个思路不行吧
如果是{[}, 这个greedy办法会把三个都delete，而最优方案是只删中间一个。
https://lee ...

我看了下你的代码，不是问要删除多少个字符。是要返回删除之后的字符串。

比如输入
abc ( ) { [ } ] ) def
返回
abc ( ) [ ] def 或者 abc ( ) { } def

我谨慎怀疑出题人兴许觉得  ( [[[ ) ( ]]] ) 这种算match，建议碰到的同学先问一下

sandreandre 发表于 2022-2-8 22:31
我覺得你可以看一下301? 你把其中一個字元拿掉再去做dfs and check the error number of parentheses

我现在能想到的也是利用301递归的思路。
前面利用LC20的思路去判断是否有效，但如果无效很难确定要上那个括号，以及删除多少。

plich 发表于 2022-2-8 23:36
我谨慎怀疑出题人兴许觉得  ( [[[ ) ( ]]] ) 这种算match，建议碰到的同学先问一下

我不确定具体的题目，只是看到论坛里面有人说了这个follow up.
但感觉括号匹配应该和代码一样， ( [[[ ) ( ]]] ) 不算match

ppscyye 发表于 2022-2-8 21:39
我现在能想到的也是利用301递归的思路。
前面利用LC20的思路去判断是否有效，但如果无效很难确定要上那 ...

我的意思是說，算一算他的invalid parenthes 多少，如果妳把這個括號拿掉導致invalid parentheses 變多就不要做dfs
def removeInvalidParentheses(self, s: str) -> List[str]:
         #check_err改成{[()]} 看看有多少個invalid parentheses
        def check_err(s):
            if not s:
                return 0
            left = 0
            right = 0
            for char in s:
                if char == '(':
                    left += 1
                elif char == ')':
                    if left != 0:
                        left -= 1
                    else:
                        right += 1
            return left + right
        
        def dfs(curr, err_num):
            if err_num == 0:
                res.append(curr)
            for i in range(len(curr)):
                new_s = curr[:i]+curr[i+1:]
                new_err = check_err(new_s)
                # 如果new_err的invalid 括號變少就dfs
                if new_err < err_num and new_s not in visited:
                    visited.add(new_s)
                    dfs(new_s, new_err)
                    
        visited = set()
        res = []
        dfs(s, check_err(s))
        return res

我觉得这个followup只能用backtracking 穷举。
用stack 或者blance都是greedy的思路， 其前提是，最近的pair一定是最后配对在一起的。所以看到就可以消掉。
但是如果可以删除，整个问题就变了，因为没法判断现在多余的closing，是否可以跟后面的配对，形成更优解。
打个极端的例子, ( {{{{{ ) }}}}} 最优解是去掉(), 但是没有全局信息，是没有办法作出这个判断的。

plich 发表于 2022-2-8 23:36
我谨慎怀疑出题人兴许觉得  ( [[[ ) ( ]]] ) 这种算match，建议碰到的同学先问一下

我也是这么怀疑的！！ 不然这个follow up和之前的解法太脱节，太怪了（当然也可能是我太菜了- -）。

ppff2460 发表于 2022-2-9 10:24
我也是这么怀疑的！！ 不然这个follow up和之前的解法太脱节，太怪了（当然也可能是我太菜了- -）。

我本觉得这题不错，抄了拿去面下一个幸运儿。
仔细一看难度不对劲儿啊。。。