言語は Python3 でやってます。

問題

https://leetcode.com/problems/assign-cookies/description/

括弧（(,),{,},[,]）の始まりと終わりのみで構成される文字列を渡されるので、正しい形になっているかどうかを確認する。

正しい、とは以下の条件を満たしていることをいう。

1. 括弧が始まっていたら、同じタイプの括弧で閉じられていること
2. 括弧の始まりは正しい順序で閉じられていること
3. 全ての閉じ括弧には、同じタイプの対応する開き括弧があること

誤った解答

class Solution:
    def isValid(self, s: str) -> bool:
        valid = 0
        for i in s:
            if i == "(":
                valid += 1
            elif i == ")":
                valid -= 1
            elif i == "{":
                valid += 10
            elif i == "}":
                valid -= 10
            elif i == "[":
                valid += 100
            elif i == "]":
                valid -= 100
            if valid < 0:
                return False
        if valid == 0:
            return True
        return False

これは勘違いしていて、2.の条件を捉え違えていた。

例えば、([)]というのは正しい順序で閉じられていないが、上記だとこれをTrueとして返す（それが正しいと思い込んでいた・・・）

解答 ①

class Solution:
    def isValid(self, s: str) -> bool:
        brakets = {"(": ")", "{": "}", "[": "]"}
        stack_start_brakets = []
        accept_end_braket = ""
        for b in s:
            if b == "(" or b == "{" or b == "[":
                stack_start_brakets.append(b)
                accept_end_braket = brakets[b]
                continue
            if b == accept_end_braket:
                del stack_start_brakets[-1]
                if len(stack_start_brakets):
                    accept_end_braket = brakets[stack_start_brakets[-1]]
                else:
                    accept_end_braket = ""
                continue
            return False
        if len(stack_start_brakets):
            return False
        return True

以下の通り動作する。

1. 括弧の対応表をdictで作る
2. 一文字ごとに以下の処理を行う a. 「括弧の始まり」だった場合は、その文字をリストに格納し、対応表から終わりの括弧を取ってきて、「許容する終わりの括弧」として保持する。 b. 「括弧の終わり」だった場合は、さらに分岐。 ⅰ. 「許容する終わりの括弧」の場合は、リストの末尾を削除&「許容する終わりの括弧」を再設定（リストの末尾から再設定 or リストの中身がなければブランクにする）。 ⅱ. 「許容する終わりの括弧」でない場合は、その時点でFalseを返す。
3. 上記が全部終わったら、リストの長さを確認し、0ならTrueを返す。

条件1は3のプロセスで最終的に担保し、 条件2と3は2のプロセスで担保している。

上記のコードをもうちょっと詰めると、以下のとおりになる。

解答②

class Solution:
    def isValid(self, s: str) -> bool:
        brakets = {"(": ")", "{": "}", "[": "]"}
        stack_brakets = []
        for b in s:
            if b == "(" or b == "{" or b == "[":
                stack_brakets.append(b)
            elif len(stack_brakets) and b == brakets[stack_brakets[-1]]:
                del stack_brakets[-1]
            else:
                return False
        if len(stack_brakets):
            return False
        return True

思ったこと

最初の勘違いはともかくとして、アプローチは最初から正しいものを出せるようになってきている反面、コードが冗長になりがちな癖があるので、適切に縮めたい。