[LeetCode - C] 20. Valid Parentheses

Valid Parentheses - LeetCode

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.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

---

Solution 1

 

stack을 이용한 방법

 

여는 괄호는 push(여는 괄호)한다.

 

닫는 괄호는  pop()한 것과 짝을 맞춰본다.

 

모든 문자 확인 후 stack이 비어있다면 true

 

채점이 계속 이상하게 되길래 discuss 확인해보니

 

전역 변수 선언해둬서 tc를 돌리는데 영향을 주나 보다.

char stk[10000];
int top = -1;

void    push(char c)
{
    stk[++top] = c;
    return 0;
}

char    pop(void)
{
    if (top < 0)
        return 0;
    return stk[top--];
}

void    isEmpty(void)
{
    top = -1;
    return 0;
}

bool isValid(char *s)
{
    char    c;
    
    isEmpty();
    while (*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')
            push(*s);
        else if (*s == ')' || *s == '}' || *s == ']')
        {
            c = pop();
            if (!((*s == ')' && c == '(') || (*s == '}' && c == '{') || (*s == ']' && c == '[')))
                return false;
        }
        s++;
    }
    return (top == -1);
}

---

총평

 

처음에는 조건 처리하여 해결하려 했는데

 

생각해보니 스택 이용하면 된다.