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

zhqfox 发表于 2022-2-8 00:14
小括号你要是给正反扫两遍的答案，铁定跟一个follow up让你只扫一遍。

请问扫一遍是用stack代替反向扫么？

lennon310 发表于 2022-2-8 14:50
请问扫一遍是用stack代替反向扫么？

其实stack那个走一遍，和反扫一遍没啥区别。

最优解不是stacking and pop么

求问fb高频题哪里找？

同问，蹲一个

感觉就是stack解法的follow up？用三个stack 分别记录（，]和}的index。以小括号举个例子，如果遇到的是）分别peek 记录三个stack栈顶元素，只有当（的index大于]和}的index时（说明不存在交叉的情况）才不需要删除，否则就是要删除的。之后的做法和1249的stack解法基本一样

动态规划。
F[i][j]表示[i,j]这个区间完成匹配最少需要删多少括号。
转移方法
F[i][j] = min{F[i][k] + F[k+1][j]} 或者 i,j如果匹配则f[i+1][j-1]
这样是O(N^3)
可能满足四边形不等式可以优化到
O(N^2)

想法不成熟。删除了。

这个follow up真的能greedy O(n)解决吗？ 我怀疑是不是面试官的意思是只要每个括号类型匹配就行了？比如{ ( } ) 的话，{ 和(都能配平不考虑中间穿插的。我的trash code... edge cases 不work。
def min_remove(s):
    """
    假设三种括号类型：(), [], {}
    """
    open_brackets = {"{":"}", "[":"]", "(":")"}
    close_brackets = {"}":"{", "]":"[", ")":"("}
    """
    stack里存着等待match的开括号(, [, {
    valid_indices存着最终可以纳入返回结果的括号的index。
    """
    stack, valid_indices = [], []

    for i in range(len(s)):
        symb = s[i]
        if symb in open_brackets:
            stack.append(i)
        elif symb in close_brackets:
            """
            如果遇到close，立刻检查stack里的顶部可否match（greedy?..)
            如果可以，开闭括号的indices放入valid_indices.
            不然，丢弃闭括号，因为想让更多的开阔号去match后面可能存在的比括号。
            """
            if stack and close_brackets[symb] == s[stack[-1]]:
                valid_indices.append(stack.pop())
                valid_indices.append(i)

    res = []
    for i in range(len(s)):
        if s[i] not in open_brackets and s[i] not in close_brackets:
            res.append(s[i])
        elif i in valid_indices:
            res.append(s[i])
    return "".join(res)

print(min_remove("[a{b]}"))
print(min_remove("abc({d}ef])hig"))
print(min_remove("abc{ds[d}][e}e]{}{]"))
print(min_remove("[(])"))
print(min_remove("[{(]   ()[][]"))
print(min_remove("[{(]   ))"))
"""
下面的不work
"""
print(min_remove("[{(]   [{]"))
print(min_remove("[{(]"))

toughcharlie 发表于 2022-2-8 15:51
想法不成熟。删除了。

还是发了哈哈，第一次和别人交流算法有点不好意思~ 有误请正。

以下是我一些原创思考：

Definition 1. Reducing a parentheses string: 对于一个 paren string s, 我们可以移除一对括号。比如， { ( ) } -> { }

Lemma 2. 对于任何一个 paren string，存在可能不唯一的 non-reducible parentheses strings or an empty string.
显然。

Algorithm 3: get the non-reducible parentheses strings by one pass: 对于每个字符，如果和 stack 的 top 匹配，则 pop；不匹配，则将当前字符和 top 写入一个队列。这个队列最后就是 non-reducible paren string.
Corollary 4. A valid/balanced parentheses string's non-reducible paren string is empty.

Theorem 5. Remove any of the non-reducible paren strings, the rest string is valid.

所以这题就是对定理 5 的直接应用。

Theorem 6: for every pair of adjunct entries of non-reducible paren string, it represents a valid substring.

事实上， finding the longest paren string 就可以用这个方法做. 只不过那个问题我们不必要知道 non-redicible paren string 的结构，所以用 max-left，min-left 的区间法最好实现就是了。

所以这题我认为是这样的：