Python学習日記——有効なかっこ

13037 ワード

Python学習日記014-有効なかっこ
題名の出所:LeetCode問題ライブラリ――有効な括弧は‘(’,‘)’,‘[’,‘],‘{’,‘}’だけを含む文字列を与えて、文字列が有効かどうかを判断する.有効な文字列は、左カッコと同じタイプの右カッコで閉じる必要があります.左かっこは正しい順序で閉じなければなりません.注意空の文字列は有効な文字列とみなされます.Example 1:入力:「()」出力:true Example 2:入力:「()[]{}」出力:true Example 3:入力:「(」出力:false Example 4:入力:「([)]出力:false Example 5:入力:{[]}」出力:trueリンク:https://leetcode-cn.com/problems/valid-parentheses
有効なカッコこの問題については,まず2つのモジュールに分けて考えることができる.1つは空の文字列で、1つは空ではない文字列です.空の文字列の場合、trueとして返されます.空でない文字列については、「スタック」の考え方で、新しい配列を作成し、文字列の要素を配列に順次追加し、追加するたびに「有効なかっこ」:有効なカッコが含まれていない場合は、引き続き追加します.「有効なカッコ」が含まれている場合は、まずこの有効なカッコのペアを削除します.その後、追加を続行します.最後にこの配列が空の配列である場合、すべてのカッコが法則に従ってペアリングできる残りのカッコを見つけたことを示します.この文字列は有効で、trueを返します.最後にこの配列が空の配列でない場合、カッコが法則に従ってペアリングに成功しなかったことを示し、falseを返します.具体的な実現過程は以下の通りである.
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0:     #    
            return True
        else:    #     
            tem = [s[0]]     #                
            j = 0     #  j              
            for i in range(1,len(s)):
                if len(tem) >= 1:
                    tem.append(s[i])    #               
                    if tem[j] == "(" and tem[j+1] == ")": 
                        tem.pop()   #           ,    
                        tem.pop()   #          
                        j -= 1    #   ,                
                        if j < 0:  #         0  
                            j = 0
                    elif tem[j] == "[" and tem[j+1] == "]":
                        tem.pop()
                        tem.pop()
                        j -= 1
                        if j < 0:
                            j = 0
                    elif tem[j] == "{" and tem[j+1] == "}": 
                        tem.pop()
                        tem.pop()
                        j -= 1
                        if j < 0:
                            j = 0
                    else:
                        j += 1
                else:
                    tem.append(s[i])
                    continue
            if tem == []:   #     ,                
                return True
            else:
                return False
                

最内層のif、elif、elif制御文の3つの条件は、次のようにマージできます.
if (tem[j] == "(" and tem[j+1] == ")") or (tem[j] == "[" and tem[j+1] == "]") or (tem[j] == "{" and tem[j+1] == "}"): 
              tem.pop()
              tem.pop()
              j -= 1
              if j < 0:
                    j = 0

ここでは制御条件を箇条書きに展開して説明するが,筆者はより理解しやすいと考える.
注意力ボタンの評論区で1種のとても簡便な解法を見て、筆者の方法と異曲同工のところがあって、しかし実現して非常に多く簡略化して、ここで学習の参考に供します:
class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''
        

学習の過程で,指摘を歓迎する.