LeetCode 20. Valid Parentheses を完全に理解する by TypeScript

Valid Parentheses

問題文

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.

日本語 by DeepL

文字 '(', ')', '{', '}', '[', ']' のみを含む文字列 s が与えられたとき、その入力文字列が有効かどうかを判定せよ。

入力文字列が有効であるのは、以下の場合である。

開き括弧は、同じ種類の括弧で閉じなければならない。
開いている括弧は正しい順序で閉じなければならない。

例題

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

検討

シンプルで簡単そうだが、これが意外と難しい。
この問題はコーディングよりも考え方のほうが難しいと思う。
一番簡単に考えると、開始カッコと終了カッコの数が一致していれば良さそうだ。
ただ、先に終了カッコが来ていたらNGである。
たとえば()はOKだが)(はNGなのだ。
そうなると終了カッコが来たときに、前に開始カッコがあればOK……なのかというと、そうでもない。
([)]このケースは開始と終了の数があっているし、終了カッコの前に開始カッコがある。条件を満たしているようだがinValidなケースである

で、どう考えるかというと……。
()の場合
まず、開始カッコが来たときに配列に追加する。
( => [(]
終了カッコが来たら、ひとつ前の文字が同じペアの開始カッコだったら配列から消す。
そうすると配列が空になる。
上記を繰り返し、最終的に配列が空だったときはtrue,それ以外はfalseとなる。

さっきの([)]の場合
([が配列に追加→)が来たので前の文字を見る→ペアではないのでNG

``(){}[]の場合 (->)ペアで消える{}ペアで消える[]ペアで消えるでOK```

というような感じ。
ペアにして消していくというイメージが掴めたら実装は簡単。

回答

  /* 文字列を配列にする */
  const strintList = s.split("");

  /* 文字をためていく配列 */
  let stackList: string[] = [];

  /*
    今回の文字が引数
    開始カッコなのかをbooleanで判定する関数
  */
  const isStartString = (str: string): boolean => {
    if (str === "{") return true;
    if (str === "[") return true;
    if (str === "(") return true;
    return false;
  };

  /* 終わりカッコを与えると開始カッコが返ってくる関数 */
  const getStartString = (str: string): string => {
    if (str === "}") return "{";
    if (str === "]") return "[";
    if (str === ")") return "(";
    return "";
  };

  /*
    終わりカッコと文字をためていく配列を引数に取る。
  */
  const deleteStartString = (endStr: string, stackList: string[]): string[] => {
    /* 配列の一番最後に追加された文字を確認する */
    const lastStack = stackList[stackList.length - 1];

    /*
      最後に追加された文字が、今回の終わりカッコに対応する始まりカッコでなければエラーだ
      エラーという文字列を返すと長さが0にならないのでエラーになる
    */
    if (lastStack !== getStartString(endStr)) {
      return ["error"];
    }

    /* 開始カッコを取得する */
    const startStr = getStartString(endStr);

    /* 開始カッコのindexを取得する */
    const index = stackList.lastIndexOf(startStr);

    /*
      開始カッコがなければそのままstackListを返す
      つまり文字を消していないのでエラー扱い、falseになる
    */
    if (index === -1) return stackList;

    /* 
      stackListから今回の終わりカッコに対応したはじまりカッコを削除する
    */
    stackList.splice(index, 1);
    return stackList;
  };

  for (let i = 0; i < strintList.length; i++) {
    /* 今回の文字 */
    const element = strintList[i];

    /* 今回の文字がはじまりカッコであれば、stackListに追加する */
    if (isStartString(element)) {
      stackList = [...stackList, element];
    } else {
      /* 終わりカッコのときは、ペアとなるはじまりカッコを消す */
      stackList = deleteStartString(element, stackList);
    }
  }
  /* スタックリストの長さが0であればtrue,0でなければfalse */
  return stackList.length === 0;
}

そんな感じで考え方がわかれば大丈夫。
leetcodeで問題を解いているとき、たまにtimeアップでNG判定になることがある。
そういう場合はdebugでconsole.logを使っていたら消してみよう。
計算量が問題じゃなくて、stdoutが問題でタイムアップになっているときがたまにある。
量の多いテストケースの場合、console.logでめちゃくちゃ時間が掛かってしまうのだ。