Neat Stack & Map Solution in java


  • 1
    T

    Used a map to keep opening-closing brackets, when an opening bracket is seen I pushed the closing bracket to the stack. O(n) time and O(n) space complexity.

     public class Solution {
            
            public boolean isValid(String s) {
                Stack<Character> stack = new Stack<Character>();
                Map<Character,Character> brackets =  new HashMap<Character,Character>();
                brackets.put('{','}');
                brackets.put('(',')');
                brackets.put('[',']');
                
                for (int  i = 0; i < s.length(); i++) {
                    char c= s.charAt(i);
                    Character closingChar = brackets.get(c);
                    if (!stack.empty() && stack.peek() == c) {  //Check if this is a correct closing bracket
                        stack.pop();
                    } else if (closingChar != null) {  //check if this is an opening bracket
                        stack.push(closingChar);  //if so add the related closing bracket to the stack
                    } else {
                        return false; //for each other case return false
                    }
                }
                
                return stack.empty();
            }
        }

  • 1
    B

    Yeah, it's neat, and it's neater in Python

    class Solution:
    # @return a boolean
    def isValid(self, s):
        stack = []
        table = {
            ')': '(',
            ']': '[',
            '}': '{',
        }
        for x in s:
            if x in ['(', '[', '{']:
                stack.append(x)
            else:
                if not stack or stack[-1] != table[x]:
                    return False
                else:
                    stack.pop()
        return not stack
    

  • 0
    T

    its always neater in python :) thats the purpose of scripting languages


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.