LeetCode 20 – Python 3 (Week 1 – 02)

Solution 1 (Runtime: 40 ms Memory Usage: 13.9 MB)

Tclass Solution:
     def isValid(self, s: str) -> bool:
    #The last character should be the corresponding bracket of the first character, thus, we can use stack.
    #One open bracket must be closed by the same type of close bracket. So, we can use dictionary.

    stack = []
    bracket = {'(':')', '{': '}', '[' : ']'}

    for parenthes in s:
        if parenthes in bracket:
            stack.append(parenthes)

        elif len(stack) == 0 or parenthes != bracket[stack.pop()]: #parenthes != bracket[stack.pop()] or len(stack) == 0 is not right
            return False

    return len(stack) == 0 #All open brackets have same type of close brackets.

Time complexity is O(n). Space complexity is O(n).

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: