LeetCodeのJavaScript解答第20題:有効括弧(Valid Partheses)

Time:2019/4/11 Title:Valid Parthentheses Difficulty:Easy Author:小鹿
テーマ:Valid Partheses
Given a string containing just the characters '(',')','{','}','[' and ']',determine if the input string is valid.
An input string is valid if:

Open brakets must be closed by the same type of braackets.

Open brakets must be closed in the corectorder.

Note that an empty string is also consided valid.
与えられた一つは'('、')'、'{'、'}'、'['、']'の文字列だけを含み、文字列が有効かどうかを判断する.
有効な文字列を満たす必要があります.

左括弧は同じ種類の右括弧で閉じなければなりません.

左括弧は正しい順番で閉じなければなりません.

注意空の文字列は有効な文字列と考えられます.
Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solve:
πアルゴリズムの考え方
まず、上記の例を通して、どのようなかっこが複合物の条件に合致するかを分析できます.

第1種(ネストされていない場合):{} [];

第二の種類(入れ子の場合):{ [ ( ) ] }.

この二つの場合を除いては条件に合致していません.
2、そして、これらの括弧を右から左にスタック構造として見て、右側はスタックトップ、左側はスタックの尾です.
3、コンパイラの中の括弧の左括弧があれば、スタックに入れます.右括弧であれば、スタックの一番上の要素を取り出してマッチングを確認します.(あらかじめペアの括弧をキーペアで残しておく)
4、もし合ったら、倉庫から出ます.そうでないとfalseに戻ります.
πコード実現
下のコードは標準的なLeetcodeテストでは最も省メモリと効率が高くないです.Mapを使っています.

var isValid = function(s) {
    let stack = [];
    //           
    let map = new Map();
    map.set(")","(");
    map.set("]","[");
    map.set("}","{");
	//          
    for(let i = 0; i < s.length; i++){
        let c = s[i];
        //      ，              
        if(map.has(c)){
            //        0
            if(stack.length !== 0){
                //         ，    false
                if(stack.pop() !== map.get(c)){
                    return false;
                }
            //         ，  false
            }else{
                return false;
            }
        }else{
            //      ，   
        	stack.push(c);
        }
    }
    //     ，        
    return stack.length === 0;
};
let str = "({(})";
console.log(isValid(str));

πコードの改善
1)この改良用のオブジェクトはMapに取って代わられ、メモリ空間が節約されました.
2)判断時に、あらかじめ格納されている構造を用いずに、左括弧に遭遇した場合にそのままスタックに入れることで、実行効率が向上します.

var isValid = function(s) {
    let stack = [];
    var obj = {
        "]": "[",
        "}": "{",
        ")": "(",
    };

    for(var i = 0; i < s.length; i++) {
        if(s[i] === "[" || s[i] === "{" || s[i] === "(") {
            stack.push(s[i]);
        } else {
            var key = stack.pop();
            if(maps[key] !== s[i]) {
                return false;
            }
        }
    }
    if(!stack.length) {
        return true;
    }
    return false;
};

π複雑度分析
時間複雑度:O(n).文字列の中の文字を巡回するだけで、入力とスタックの時間の複雑さはO(1)です.
空間複雑度:O(n).左括弧の近くしかない場合、右括弧がマッチしていない場合は最悪の場合、すべての括弧がスタック内にあります.例えば:{{{{{{{{{{{{{{{{}
LeetCode開源Github倉庫に一緒に参加してください.他の言語のコードを私に提出してもいいです.倉庫では友達と一緒にカードを打つことを堅持します.私達のオープンソース倉庫を共同で改善します.Github:https://github.com/luxiangqiang/JS-LeetCode
私の個人番号に注目してください.「平凡に甘んじない私たち」は自分でプログラミングした物語を記録しました.