[データ構造/アルゴリズム]211029カッコを検索stackカッコを使用するreduce

📌 balancedBrackets

文字列を受け入れ、文字列内のすべてのカッコが一致しているかどうかを返します.

注意事項

かっこのタイプは、(,)のみを考慮します.

カッコは、まず()を開いてから()を閉じなければなりません.

の空の文字列が受信された場合、trueを返す必要があります.

I/O例

let output = balancedBrackets('(');
console.log(output);////-> false

output = balancedBrackets('()');
console.log(output);//--> true

Advanced

すべてのタイプのカッコ((()、{、}、[、])を含む文字列を入力し、すべてのカッコが一致するかどうかを返します.

let output = balancedBrackets(' {}'); console.log(output); // --> true

output = balancedBrackets('[({})]'); console.log(output); // --> true let output3 = balancedBrackets('[(]{)}'); console.log(output); // --> false この問題も理解するのに10分かかりましただから最初は変なコードを出して『そうじゃないの?やったようだしかし、おかしいことに、テストケースの部分が合格し、少し驚きました。しかし、ベストプラクティスではスタックが使用されています。 第一の方法 文字列数が0の場合は返されます(注意)。また、文字列の個数が1の場合、カッコにかかわらずfalseを返します。これらの状況は先に排除された。したがって、作成されたコードは以下のようになります。 if(str.length === 0) { return true } else if(str.length === 1) { return false } for(let i=0; i<str.length; i++ ) { for(let j=1; j<str.length; j++) { if(str[i] === '(' || str[j] === ')') { return true } else if(str[i] === '{' || str[j] === '}') { return true } else if(str[i] === '[' || str[j] === ']') { return true } else { return false } } } } 2つの重複文を開いたり閉じたりするときにtrue処理を行います。そうしないとfalseが返されます。これにより,"()()"[(])}""[]}()"の3つのケースを通過することができない. 第2の方法 だから見つけたもう一つの方法はreduceを使うことです。入力した文字列とは異なり、オブジェクトは変数に割り当てられ、キー値にはオープンカッコ、値には終了カッコが含まれます。このコードはreduceがうまく書けないとかえって悪くなります。 let bList = { "(" : ")", "{" : "}", "[" : "]" } let verify = str.split('').reduce(function(ac, cv) { if (cv === bList[ac[ac.length - 1]]) { ac.pop(); } else { ac.push(cv); } return ac; }, []); return verify.length === 0; } 繰り返し文で、カッコ配列の現在の要素(cv)がキー値としてカッコオブジェクト(bList)に存在する場合、空の配列verifyの最後に値が追加されます。 キー値として存在しない場合は、verify配列の最後の要素の値をキー値として使用してbListのvalueを検索します。現在の要素がこのvalue値と同じ場合、ペアになるためverify配列から最後の要素が削除されます。 verifyが空の配列の場合、trueが返され、そうでない場合falseが返されます。 ソース

レコードコード

転送コードは上のコードの方向と似ていますが、私はもっと理解しやすいです.このコードには3つの変数が割り当てられます.1つはスタックとして使用される空の配列であり、キー値にオープンカッコ、価値値に終了カッコを含むオブジェクトが含まれ、最後にCloser変数が割り当てられます.

const stack = [];
const opener = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
const closer = '}])';
for (let i = 0; i < str.length; i++) {
    if (str[i] in opener) {
      stack.push(str[i]); //1)
    } else if (closer.includes(str[i])) {
      const top = stack.pop();
      const pair = opener[top];
      if (pair !== str[i]) {
        return false; //2)
      }
    }
  }
  return stack.length === 0;//3)
}

1)開口器内str[i]がキー値である場合、スタック内でpush
2)closer変数にstr[i]が含まれている場合、開いている変数の最上位がstr[i]と一致しない場合、falseが返されます.
3)スタックが空の場合、すべてのカッコが正しく一致していることを示し、trueを返します.