LeetCode 20. Valid Parentheses ( C ) – Easy

判斷 ( ) 、 [ ] 、 { } 等是否有配對。

原文題目如下

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 1:

Input: s = "()"
Output: true
Example 2:

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

Input: s = "(]"
Output: false
Example 4:

Input: s = "([)]"
Output: false
Example 5:

Input: s = "{[]}"
Output: true
 
Constraints:

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

解題策略為透過堆疊 ( Stack ) ，來比較是否都有配對到。

下面是我的程式碼

bool isValid(char * s){
    char stack[5000];
    int top = 0;
    for(int i = 0;i<strlen(s);i++){
        if(s[i] == '(' || s[i] == '[' || s[i] == '{' ){
            stack[top] = s[i];
            top++;
        }
        else if(s[i] == ')'){
            if(top==0)
                return false;
            else if(stack[top-1] == '('){
                top--;
            }
            else{
                return false;
            }
        }
        else if(s[i] == ']'){
            if(top==0)
                return false;
            else if(stack[top-1] == '['){
                top--;
            }
            else{
                return false;
            }
        }
        else if(s[i] == '}'){
            if(top == 0)
                return false;
            else if(stack[top-1] == '{'){
                top--;
            }
            else{
                return false;
            }
        }
        else{
            return false;
        }
    }
    
    if(top != 0)
        return false;
    
    return true;
}

下面是時間與空間之消耗

Runtime: 0 ms, faster than 100% of C online submissions for Remove Nth Node From End of List.

Memory Usage: 5.7 MB, less than 64.50% of C online submissions for Remove Nth Node From End of List.

下一題連結 : LeetCode 21. Merge Two Sorted Lists ( C ) – Easy