Zenn
😅

LeetCode 20. Valid Parentheses

2021/11/24に公開
Kotlin
LeetCode
tech

Question

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.

文字 '('、')'、'{'、'}'、'['、']'だけを含む文字列 s が与えられたとき、入力文字列が有効かどうかを判断する。

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

  1. 開いた括弧は、同じ種類の括弧で閉じなければならない。
  2. 開いた括弧は正しい順序で閉じなければならない。

Code

class Solution {
    fun isValid(s: String): Boolean {

        val bracket = mapOf<Char, Char>(')' to '(', ']' to '[', '}' to '{')
        val stack = mutableListOf<Char>()
        for (char in s) {
            if (char in bracket.values) {
                stack.add(char)
            } else if (stack.isNotEmpty() && bracket[char] == stack.last()) {
                stack.removeAt(stack.lastIndex)
            } else {
                return false
            }
        }
        return stack.size < 1
    }
}

文字列sを一文字ずつChar型としてLIFOなstackに詰めながら考えるとよい

openなbracket((, [, {)が来たら、stackに詰めていき、
closeなbracket(), ], })が来たら、stackのpeekな位置に対応するopenなbracket((, [, {)(HashMapで定義しておく)があることを確認して、popする。
<T> Iterable<T>.last()を行うときはなんらかのbracketが必ず返ることを前提としているので、<T> Iterable<T>.isNotEmpty()などで、チェックをしておくこと。

上記ができない時点でinvalidな並びとなるのでfalseを返す。

文字列sを走査し終えた時点で、stackが空なら文字列sに対してLIFOで正しく処理できたことになるので、trueを返せるが、この時点でstackに何かしら残っている場合、対応しなかった場合が浮き彫りになるのでfalseとして返す。

時間計算量はO(n)で、調べた感じ似たような方法が多かった。

Profile

  • Runtime: 160 ms
  • Memory Usage: 35.5 MB

Submission

GitHubで編集を提案

Discussion