检查字符串是否包含一组有效的括号，字符串可能包含笑脸和皱眉脸

Question

最近我参加了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"

我知道代码在做什么，但不能说服自己相信它的正确性或证明。我们如何证明它总是有效的呢？

Answer 1

你可以这样理解它：

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