🖋

LeetCode 20. Valid Parentheses

に公開

はじめに

LeetCode 「20. Valid Parentheses」の問題をGoで解きました。

問題

https://leetcode.com/problems/valid-parentheses/description/

問題文

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)
GitHubで編集を提案

Discussion