Leetcode 20 Valid Parentheses

1. Description

Given a string s containing just the characters '(', ')', '{', '}', '[', ']', 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.

Constraints:

\(1 \leq s.length \leq 10^{4}\)
s consists of parentheses only '()[]{}'.

1.1. Examples:

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

2. Solution

2.1. Understanding the problem

Looking at this question I think this is a Stack question with First In Last Out (FILO).

A more complicated valid example would be ({[]}).

2.2. Algorithm

Because \(s.length \geq 1\), let's start with having 1 element in the string, which is obviously invalid. What's more, we know that for any s, if \(s.length \mod 2 = 1\), then it's an invalid string because there will always be one bracket left.

Given the above, we will only consider \(s.length \mod 2 = 0\), and because \(s.length \leq 10^{4}\), which is relatively a small number, we can apply the following algorithm

Scan the string one by one from left to right (order doesn't really matter here).
If the stack is not empty, check to see if the new element can pair with the last element in the stack
1. If they can pair, then pop the last element from the stack and go back to step 1.
2. If they cannot pair, then push the element in to the stack as the last element and go back to step 1.
If the stack is empty, simply push the element into the stack and go back to step 1.
Continue the process until we scanned all elements in the string.
If the stack in the end is empty, then we return true, else return false.

2.3. Code

Listing 1: 20 valid parentheses my solution

def isValid(s):
    """
    :type s: str
    :rtype: bool
    """
    if len(s) % 2 == 1:
        return False

    # by definition, we should only have one way (open -> close) mapping
    mapping = {
        "(": ")",
        "[": "]",
        "{": "}",
    }
    stack = []
    for element in s:
        if len(stack) == 0:
            stack.append(element)
        else:
            if mapping.get(stack[-1], None) == element:
                stack.pop()
            else:
                stack.append(element)

    return len(stack) == 0
# invalid
print(isValid(")"))
print(isValid("(){}}[]"))
print(isValid("}}]"))
# valid
print(isValid("()"))
print(isValid("(){[]}()}"))
print(isValid("({}){[]}()}"))

Listing 2: 20 valid parentheses my solution-results

False
False
False
True
True
True

2.3.1. Complexity

2.3.1.1. Time complexity:

\(O(N), \text{where } N=s.length\) as it's just one scan.

2.3.1.2. Space complexity:

\(O(N), \text{where } N=s.length\). It's the space needed for the stack.

2.4. Leetcode solution

I'll not provide Leetcode solution because I don't want to accidentally leak their IP as I'm on a premium plan at the moment.

However my solution is almost the same as the leetcode solution.

Listing 3: 20 valid parentheses leetcode solution

<<imports for typing>>

Listing 4: 20 valid parentheses leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

nil.