LeetCode 20. Valid Parentheses
はじめに
LeetCode 「20. Valid Parentheses」の問題をGoで解きました。
問題
問題文
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
が与えられたとき、その入力文字列が有効かどうかを判定する。
入力文字列が有効であるのは、以下の場合である:
1.開き括弧は、同じ種類の括弧で閉じなければならない。
2.開き括弧は正しい順序で閉じなければならない。
3.どの閉じ括弧にも、対応する同じ型の開き括弧がある。
例
Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Input: s = "([])"
Output: true
制約
1 <= s.length <= 104
-
s
consists of parentheses only'()[]{}'
.
解答
この問題で、括弧が正しい順序で閉じられているかを判定するには、最後に開いた括弧が最初に閉じられる必要があります。
これは LIFO(Last-In-First-Out) の構造である スタック(Stack) を用いるのが有効です。
コード
func isValid(s string) bool {
stack := []byte{}
pairs := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
for i := range s {
c := s[i]
if c == '(' || c == '[' || c == '{' {
stack = append(stack, c)
} else {
if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
map[byte]byte
を使って、閉じ括弧→開き括弧の対応表を作っており、それによりロジックがシンプルになります。
空のスタックを用意し、s
を走査して開き括弧の場合はスタックにpushします。
閉じ括弧の場合は以下を行います。
- スタックが空ならfalse
- スタックの一番上を確認し、対応する開き括弧でなければfalse
- 対応していればスタックからpop
ループを抜けた後、スタックが空であればtrueを返します。
計算量
- 時間的計算量:O(n)
- 空間的計算量:O(n)
Discussion