0

最近、フェイスブックのハッカーカップに参加したとき、「バランスの取れたスマイリー」という質問がありました。

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 に答える