Valid Parenthesis

Ever wondered how the compiler checks to ensure all opened parenthesis are closed and ordered correctly? Well, this is such a problem. Here you are required to return true if a provided string of parenthesis is ordered correctly and every opening parenthesis has a corresponding closing parenthesis.

Leetcode problem

Thought Process
At first glance, the problem seems straightforward. My initial approach was to use a stack to keep track of opening brackets and ensure they are properly closed in the correct order. This method leverages the Last-In-First-Out (LIFO) property of stacks, which is ideal for this type of problem.

My Code

bool isValid(String s) {
    final stack = [];

    final Map<String, String> parObj = {
        ')':'(',
        ']':'[',
        '}':'{'
    };

    for(var i in s.split('')){
        if(parObj.containsValue(i)){
            stack.add(i);
        }else if(parObj.containsKey(i)){
            if(stack.isEmpty || stack.removeLast() != parObj[i]){
                return false;
            }
        }
    }
    return stack.isEmpty;
  }

This solution works by iterating through each character in the string. If the character is an opening bracket, it is pushed onto the stack. If it’s a closing bracket, the stack is checked to ensure it matches the most recent opening bracket. If there’s a mismatch or the stack is empty when it shouldn’t be, the function returns false. Finally, if the stack is empty at the end of the iteration, the string is considered valid.​

Get Arthur Pundo’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Performance

While the above solution is correct, I wanted to ensure it was efficient. The time complexity of this solution is O(n), where n is the length of the string, since we are processing each character once. The space complexity is also O(n) in the worst case, due to the stack storing all opening brackets.​

Conclusion

Solving the Valid Parentheses problem reinforced my understanding of stack data structures and their practical applications in parsing and validation tasks.