algorithm - Facebook Hacker Cup 2013 Balanced Smileys 解释

Question

我的问题是关于 FB HackerCup 2013 QualificationRound 问题 - BalancedSmileys。

问题陈述:https://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420 (也在这里复制:https://github.com/anuragkapur/Algorithmic-Programming/tree/master/src/com/anuragkapur/fb/hackercup2013/qr#problem-2-balanced-smileys)

我想出了如何使用具有指数运行时间的 BruteForce 方法来解决这个问题。

根据发布的官方解决方案，有一个线性运行时间的解决方案。此处描述:https://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621

本质上，它维护两个计数器:minOpen 和 maxOpen。每当遇到左括号“(”时，maxOpen 都会增加。如果“(”不是笑脸的一部分，minOpen 也会增加。处理“)”的策略也类似，如上面的解释链接中所述。

我可以看到线性时间方法有效，但我的脑子里不是很清楚 - 怎么办？所以我正在对这个小组进行投票，看看是否有人可以给出线性运行时间解决方案的替代“解释”。

非常感谢!

Answer 1

预处理:对输入进行标记并将每个标记转换为一个列表，其中包含对左括号计数的可能影响。

输入

i am sick today (:()
:(:))

成为

[[0], [0], ..., [0], [1], [0, 1], [-1]]
[[0, 1], [-1, 0], [-1]]

.现在，您的蛮力算法是这样的。

def solution1(lst, opencnt=0, i=0):
    if opencnt < 0:
        return False
    elif i >= len(lst):
        return opencnt == 0
    else:
        for delta in lst[i]:
            if solution1(lst, opencnt + delta, i + 1):
                return True
        return False

函数 solution1 对于给定的输入总是给出相同的输出。对于给定的 lst，其条目在 {-1, 0, 1} 中，每个 opencnt(-1 到 len (lst)) 和 i(0 到 len(lst) - 1)，因此通过缓存给定输入的输出，即 memoizing ，我们得到二次时间算法。

线性时间算法将控制流从里到外翻转过来。我们将 opencnt 设为一个集合，而不是对每个 delta 进行单独的递归调用。

def solution2(lst, opencnt={0}, i=0):
    opencnt = {x for x in opencnt if x >= 0}
    if i >= len(lst):
        return 0 in opencnt
    else:
        return solution2(lst, {x + delta for x in opencnt for delta in lst[i]}, i + 1)

此实现还不是线性时间。最后的优化是opencnt始终是一个区间，即[minOpen, maxOpen]，可以在常数时间内操作。