Stack implementation error Leetcode Question 20

user_14416346 0
Viewed 95

The leetcode question is :

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.

My code:

class Solution:
    def isValid(self, s: str) -> bool:
    
    mapper = {')':'(',
             ']':'[',
             '}':'{'}
    
    stack = []
    top_element = -1
    
    if not s:
        return False
    
    for char in s:
        
        
        if char in mapper and top_element == -1:
            return False
        
        if char in mapper and mapper[char] == top_element:
            stack.pop()
        
        else:
            stack.append(char)
            top_element = stack[-1]
        
        
    return not stack

The logic works for '()' input but not for '{[]}'. I think the error is in the if-else condition

What am I doing wrong?

stack list python
3 Answers

The logic and your code is good, you just need to update topelement after the pop.(Change this:

if char in mapper and mapper[char] == top_element:
            stack.pop()
        
        else:
            stack.append(char)
            top_element = stack[-1] if len(stack)>0 else None

To this (with one more line the commented one):

if char in mapper and mapper[char] == top_element:
            stack.pop()
            top_element = stack[-1] #additional line
        
        else:
            stack.append(char)
            top_element = stack[-1]
user_82285580

There are several things:

class Solution:
    def isValid(self, s: str) -> bool:
                ^^^^
  1. Does this function need to be non-static?
    mapper = {')':'(',
             ']':'[',
             '}':'{'}
    
    stack = []
    top_element = -1
    
    if not s:
        return False
    
    for char in s:
        
        
        if char in mapper and top_element == -1:
            return False
        
        if char in mapper and mapper[char] == top_element:
            stack.pop()
            # Change top element
            top_element = stack[-1] if stack else -1

  1. You need to change top_element after pop.

  2. What if parenthesis is closing, but it doesn't match with top_element?

        elif char in mapper and mapper[char] != top_element:
            return False

        else:
            stack.append(char)
            top_element = stack[-1]
        
    return not stack

Also you could check if s contains other symbols than parenthesis, just in case.

user_33659220
  • You're in the right path.
  • We can just simply add a sentinel value to the stack at initialization.
  • This'd pass through:
class Solution:
    def isValid(self, base_string):
        memo = {')': '(', '}': '{', ']': '['}
        stack = [0]
        for character in base_string:
            if character in memo:
                if stack.pop() != memo[character]:
                    return False
            else:
                stack.append(character)
        return stack == [0]
user_65533280
Related