同步发于 JuzerTech 网站，里面有我软、硬件学习的纪录与科技产品开箱，欢迎进去观看。

判断 ( ) 、 [ ] 、 { } 等是否有配对。

 

题目与范例如下

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.