---
title: 'LeetCode 20. Valid Parentheses'
disqus: hackmd
---

# LeetCode 20. 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.

## Example

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

Input: s = "(]"
Output: false

## Constraints

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

## Answer

用stack的概念，因對稱所以memory只要len/2的空間就好，stack存相對應的括號，若*s不是上括號就檢查當下值是否為預先備好的對稱下括號，若不是就直接return false。檢查完的話top必為0。

bool isValid(char * s) {
    if(*s == '\0'){return true;}
    int top = 0, len = strlen(s);
    char *temp = (char *)malloc(sizeof(char)*(len/2));
    while(*s != '\0'){
        if((*s == '(' || *s == '[' || *s == '{') && top < len/2){
            if(*s == '('){ temp[top] = ')'; top++;}
            else if(*s == '['){ temp[top] = ']'; top++;}
            else { temp[top] = '}'; top++;}
        }
        else {
            if(top && *s == temp[top - 1]){
                top--;
            }
            else { 
                free(temp); 
                return false;
            }
        }
        s++;
    }
    free(temp);
    return top == 0 ? true : false;
}

## Link
https://leetcode.com/problems/valid-parentheses/
###### tags: `Leetcode`