# 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
- If they can pair, then pop the last element from the stack and go back to step 1.
- 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

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("({}){[]}()}"))

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.

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

`nil`

.