0
\$\begingroup\$

This is a Leetcode problem -

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if -

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1 -

Input: "()"
Output: True

Example 2 -

Input: "()[]{}"
Output: True

Example 3 -

Input: "(]"
Output: False

Example 4 -

Input: "([)]"
Output: False

Example 5 -

Input: "{[]}"
Output: True

Here is my solution to this challenge -

def is_valid(s):
    if len(s) == 0:
        return True
    parentheses = ['()', '[]', '{}']
    flag = False
    while len(s) > 0:
        i = 0
        while i < 3:
            if parentheses[i] in s:
                s = s.replace(parentheses[i], '')
                i = 0
                flag = True
            else:
                i += 1
        if len(s) == 0:
            return True
        else:
            flag = False
            break
    return False

So I would like to know whether I could improve performance and make my code shorter.

\$\endgroup\$
  • \$\begingroup\$ Is there a reason you are using flags? I removed the flags and it still seems to work, unless I made a mistake. Thank you. \$\endgroup\$ – moondra Jun 16 at 0:37
3
\$\begingroup\$

Not a performance suggestion, but you can make use of the fact that an empty collection is Falsey.

if len(s) == 0:

Is functionally the same as just:

if not s:

And similarly,

while len(s) > 0:

Can be just:

while s:

Relevant PEP entry (search for "For sequences" under the linked heading).

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer! Really helped a lot. I never realized this. Thanks for pointing this out. +1 \$\endgroup\$ – Justin Jun 14 at 17:29
2
\$\begingroup\$

You can make your code shorter and much faster by using stack -

Stack works on the principle of \$“\$Last-in, first-out \$”\$. Also, the inbuilt functions in Python make the code short and simple. To add an item to the top of the list, i.e., to push an item, we use the append() function and to pop out an element we use the pop() function. These functions work quite efficiently and fast in end operations.

Here's a visual representation -

enter image description here

Source - https://www.geeksforgeeks.org/stack-data-structure/

Here's a shorter and faster version of your program using stack -

def is_valid(s):
    stack = []
    mapping = {
        ")" : "(",
        "}" : "{",
        "]" : "["
    }

    if len(s) != 0: 
        for char in s: 
            if char in mapping: 
                if len(stack) == 0: 
                    return False
                else: 
                    top_element = stack.pop() 
                    if top_element != mapping[char]:
                        return False
            else:
                stack.append(char)
        return len(stack) == 0
    return True

Let's compare Leetcode timings (76 test cases) -

Your Leetcode result -

enter image description here


Leetcode result for stack solution (76 test cases) -

enter image description here

Also, you don't need any flag here (Thanks to @moondra for pointing it out) -

parentheses = ['()', '[]', '{}']
flag = False
while len(s) > 0:
     # rest of the code

Or here -

s = s.replace(parentheses[i], '')
i = 0
flag = True

Or here -

    else:
        flag = False
        break
return False

The program will work without the flags.


\$\endgroup\$
  • 1
    \$\begingroup\$ There is no need to check for len(s) == 0 as, if it is the case, the for loop wouldn't execute and len(stack) would be 0. Also, if not stack: inside the loop feels more pythonic. \$\endgroup\$ – Mathias Ettinger Jun 14 at 16:08
  • \$\begingroup\$ @MathiasEttinger - Could you include this in an answer? This seems interesting. \$\endgroup\$ – Justin Jun 14 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.