yoruru的努力日記

20. Valid Parentheses

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.
3. Every close bracket has a corresponding open bracket of the same type.

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 '()[]{}'.

SOL：

遇到左括號，放入stack；遇到右括號，判斷stack[top]是否為相對應的左括號並pop。

值得注意的是，因為s可能只輸入右括號，所以必須防止有stack[-1]這種超出index的狀況。

#define MAX_SIZE 10000

bool isValid(char * s){
    char stack[MAX_SIZE];
    int top = -1;
    for(int i = 0; s[i]!='\0'; i++){
        switch (s[i])
        {
            case '(':
            case '[':
            case '{':
                stack[++top]=s[i];
                break;
            case ')':
                if (top<0 || stack[top]!='(')
                    return false;
                else
                    top--;
                break;
            case ']':
                if (top<0 || stack[top]!='[')
                    return false;
                else
                    top--;
                break;
            case '}':
                if (top<0 || stack[top]!='{')
                    return false;
                else
                    top--;
                break;
            default:
                break;
        }
    }
    if(top>-1)
        return false;
    return true;
}

附上更精美一點的寫法：

char getChar(char c){
    switch(c) {
        case ')':
            return '(';
        case ']':
            return '[';
        case '}':
            return '{';
    }
    return '\0';
}
bool isValid(char * s){
    int len = strlen(s);
    char *stack = malloc(len*sizeof(char));
    int top = -1;
    for (int i=0 ; i<len ; i++) {
        if (s[i]=='('||s[i]=='['||s[i]=='{') {
            top++;
            stack[top]=s[i];
        }
        else {
            if (top>-1&&getChar(s[i])==stack[top]) {
                top--;
            }
            else
                return false;
        }
    }
    free(stack);
    if(top==-1)
        return true;
    else
        return false;
}