StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCheck whether a string contains valid set of parenthesis, string may contain smileys and frowny faces
text
Body
copied!<p>Recently I participated in Facebook hacker cup, there was a question named "Balanced smileys':</p> <pre><code>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 ":(" </code></pre> <p>Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced. </p> <p>I did it using recursion and it was right but time complexity was high. I thought about memoization but still time complexity will O(n^2)/O(N^3). They posted solutions in which time comlexity was O(N)!</p> <p>Solution is in python:</p> <pre><code>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" </code></pre> <p>I know what code is doing but couldn't convince my self about its correctness or proof. How can we prove that it will work always?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload