Introduction

Problem

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

An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

source: leetcode

This is an intermediate-level coding problem and is often asked in coding interviews. What makes this problem interesting is that unlike other coding problems, this one has practical applications such as mathematics or parsings.

Solution

code

def has_valid_parenthesis(statement: str):
    p_map = {
        ")": "(",
        "]": "[",
        "}": "{"
    }
    stack = []

    for char in statement:
        if char in p_map:
            if len(stack) > 0 and p_map[char] == stack[-1]:
                stack.pop()
                continue
            return False
        else:
            stack.append(char)

    return True

Explanation

Two main variables were initiated. The p_map variable simply maps the closing parenthesis to its corresponding opening. Albeit unnecessary, it makes for readability and convenience of the code thereon. The stack variable records every opening parenthesis to be matched/removed when it checks for a closing parenthesis.

The logic to this approach is fairly simple. We are to check for every character in a statement/expression. If the character is an opening parenthesis, we add it to the stack. Otherwise, we are to check if the closing parenthesis matches the last recorded opening parenthesis.

Evaluation

Time complexity: O(n)
Space complexity: O(n)

• BACK TO TOP