【LeetCode in TypeScript】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.

文字列 `s` が与えられる。この文字列には、'(', ')', '{', '}', '[', ']' だけが含まれている。入力された文字列が有効かどうかを判定せよ。

入力文字列が有効であるためには以下の条件を満たす必要がある。

• 開き括弧は同じ種類の括弧で閉じられなければならない。
• 開き括弧は正しい順序で閉じられなければならない。
• すべての閉じ括弧には対応する同じ種類の開き括弧が存在する。

I/O

Example 1:

• Input: s = "()"
• Output: true

Example 2:

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

Example 3:

• Input: s = "(]"
• Output: false

Example 4:

• Input: s = "([])"
• Output: true

解答

const brackets: { [key: string]: string } = {
  ']': '[',
  '}': '{',
  ')': '(' 
};

function isValid(s: string): boolean {
  const stack: string[] = [];
  const chars = s.split('');

  for (const char of chars) {
    if (isClosing(char)) {
      const opening = stack.pop();

      if (brackets[char] !== opening) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }

  return stack.length === 0;
}

function isClosing(s: string): boolean {
  return brackets.hasOwnProperty(s);
}

解説

この問題では、開かれた括弧が対応する閉じ括弧で正しい順序で閉じられているかを確認する必要があります。

スタックを使用するアプローチ

• 文字列を左から右に進めながら各文字を処理します。
• 開き括弧はスタックに追加し、閉じ括弧が現れた場合、スタックから括弧を取り出して一致するかを確認します。
• スタックが空でなければならないことが、最終的にすべての括弧が正しく閉じられている条件となります。
• このアプローチの時間計算量は O(n) です。

---