###### tags: `leetcode` `easy` `String` `Stack`
# [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

## Description

Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, 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.
Every close bracket has a corresponding open bracket of the same type.

## Examples
### Example 1:

**Input**: s = "()"
**Output**: true

### Example 2:

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

### Example 3:

**Input**: s = "(]"
**Output**: false

## Constraints:

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

## Code

bool isValid(char* s) {
    int strLen = 0;
    int *brackCount, *tmp;
    strLen = strlen(s);
    brackCount = calloc(strLen, sizeof(int));
    tmp = brackCount;
    for (int i = 0; i < strLen; i++) {
        switch (s[i]) {
            // Left brackets
            case '(':
                *(tmp++) = 1;
                break;
            case '[':
                *(tmp++) = 2;
                break;
            case '{':
                *(tmp++) = 3;
                break;
            // Right brackets
            case ')':
                // # of left > # of right
                if (tmp == brackCount)
                    return false;
                // Not match
                if (*--tmp != 1)
                    return false;
                break;
            case ']':
                if (tmp == brackCount)
                    return false;
                if (*--tmp != 2)
                    return false;
                break;
            case '}':
                if (tmp == brackCount)
                    return false;
                if (*--tmp != 3)
                    return false;
                break;
            // Not brackets
            default:
                return false;
        }
    }
    // # of right > # of left
    if (tmp != brackCount)
        return false;

    return true;
}

## Complexity

|Space |Time |
|- |- |
|$O(N)$|$O(N)$|

## Result

- Runtime: 6 ms, 19.05 % of c submissions
- Memory usage: 5.8 MB, 40.51 % of c submissions