0

最近参加Facebook黑客杯，有个题叫“平衡笑脸”：

A message has balanced parentheses if it consists of one of the following:

- An empty string ""
- One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
- An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.
- A message with balanced parentheses followed by another message with balanced parentheses.
- A smiley face ":)" or a frowny face ":("

编写一个程序，确定是否有一种方法可以解释他的信息，同时保持括号平衡。

我使用递归做到了，这是正确的，但时间复杂度很高。我考虑过记忆，但时间复杂度仍然是 O(n^2)/O(N^3)。他们发布了时间复杂度为 O(N) 的解决方案！

解决方案在python中：

def isBalanced(message):

minOpen = 0

maxOpen = 0



for i in xrange(len(message)):

    if message[i] == '(':

        maxOpen += 1

        if i == 0 or message[i-1] != ':':

            minOpen += 1

    elif message[i] == ')':

        minOpen = max(0, minOpen-1)

        if i == 0 or message[i-1] != ':':

            maxOpen -= 1

            if maxOpen < 0:

                break



if maxOpen >= 0 and minOpen == 0:

    return "YES"

else:

    return "NO"

我知道代码在做什么，但无法说服自己相信它的正确性或证据。我们如何证明它永远有效？

4

1 回答 1

0

你可以这样理解：

每次你遇到一个 (，它可以是一个左括号，或者是微笑的一部分，如果它在冒号之后。对于像 :() 这样的字符串，当你遇到 (时，有效左括号的最小数量为0，最大个数为1。然后你继续遍历字符串，遇到)。此时，如果最大个数为0，则整个字符串不是有效字符串，否则有效。

于 2013-02-02T14:06:24.297 回答