DAY 4 Valid Parentheses

第 11 屆 iThome 鐵人賽

DAY 4

自我挑戰組

刷題記錄與人生分享系列第 4 篇

11th鐵人賽 leetcode c javascript

keyhouse12

2019-09-05 12:07:53

1197 瀏覽

分享至

題目:

https://leetcode.com/problems/valid-parentheses/
一個字串中包含'(' , ')', '{', '}', '[' and ']'，判斷字串是否迴文。

解題思路:

先放入一個字串，利用變數紀錄目前位置，如果目前其位置與放入字串為成對時繼續其步驟，但當不成對時則立即回傳錯誤。

C版本:

bool isValid(char* s) {
    char stack[1000000];
    int top=-1;
    while(*s){
        if(*s==')'){
            if(top>=0 && stack[top]=='(')top--;
            else return false;
        }else if(*s=='}'){
            if(top>=0 && stack[top]=='{')top--;
            else return false;
        }else if(*s==']'){
            if(top>=0 && stack[top]=='[')top--;
            else return false;
        }else stack[++top]=*s;
        s++;
    }
    return top==-1;
}

Javascript版本:

var isValid = function(s) {
    var stack = [];
    var top=-1;
    
    for(var i = 0; i<s.length; i++)
    {
        if(s[i] == ")")
        {
            if(top >= 0 && stack[top] == "(")
                top--;
            else
                return false;
        }
        else if(s[i] == "]")
        {
             if(top >= 0 && stack[top] == "[")
                top--;
            else
                return false;   
        }
        else if(s[i] == "}")
        {
            if(top >= 0 && stack[top] == "{")
                top--;
            else
                return false;    
        }
        else
        {
           stack[++top] = s[i];     
        }
    }
    return top==-1;
};