Time limit exceeded in valid parentheses problem-CodePudding

I am trying to solve the following problem in python (not for anything, just trying to learn how to code), and I keep getting the time limit exceeded error.

Given a string s 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.

Can someone please explain why the code won't run?

Detail on my logic: I am trying to check if the input has any values (or else return true immediately), then whether it has any closed parentheses next to each other. The idea is that every true input must have either '()', '[]', or '{}' somewhere in the string. Then, I would remove those pairs until either there are no more characters, and I know it's true, or it can't find any and it is false.

If this is a poor way to think about the problem and you plan to offer a different way, please also help me understand why this code doesn't run.

class Solution:
    def isValid(self, s: str) -> bool:
        l = ['()','[]','{}']
        while s != '':
            while l[0] in s or l[1] in s or l[2] in s:
                try:
                    s.replace(s[s.index(l[0])],'')
                except:
                    ValueError
                try:
                    s.replace(s[s.index(l[1])],'')
                except:
                    ValueError
                try:
                    s.replace(s[s.index(l[2])],'')
                except:
                    ValueError
                continue
            return False
        return True

CodePudding user response：

s.replace(...) returns the modified string. It doesn't modify s in place; it can't, since strings are immutable.

There are other mistakes but I'll leave them as an exercise for you to figure out. Fixing this will at least get you past the infinite loop.

CodePudding user response：

Don't use `str.replace()`!

str.replace() is an O(n) operation (where n == len(s)). In the worst case, you perform the replace operation O(n) times, giving you a runtime of O(n^2). John Kugelman is right that you're not using the str.replace() function correctly, but you will still TLE even if you use it correctly.

We can do better by keeping a stack of unmatched parentheses. For each character, we do one of three things:

If it's an opening brace, add it to the stack.
If it's a closing brace, check whether it lines up with the opening parenthesis at the top of the stack; if so, pop the parenthesis off the top of the stack, so that we don't check it against future characters.
Otherwise, return False -- the string can't possibly represent balanced parentheses.

At the end of this procedure, if we have any unmatched parentheses after processing all of the closing parentheses, we want to return False. We can do this by checking whether the stack is empty after processing the string.

We make one pass through the string, doing O(1) work at each iteration. This gives us an O(n) runtime, which should solve the TLE issue:

def isValid(self, s: str) -> bool:
    stk = []
    bracket_mappings = {'(': ')', '{': '}', '[': ']'}
    for char in s:
        if char in bracket_mappings:
            stk.append(char)
        elif len(stk) > 0 and char == bracket_mappings[stk[-1]]:
            stk.pop()
        else:
            return False
    return len(stk) == 0

CodePudding user response：

In addition to the above answers, it seems like you are trying to catch a ValueError when s.index() fails.

The code you have will instead catch any exception, not just ValueError.

You can do it like this:

try:
    # try code
except ValueError as e:
    # handle ValueError

Don't use str.replace()!

Don't use `str.replace()`!