Python:CodeTaka 2週目3

Q.質問：sは複数の括弧からなるStringパラメータです。true/false、sが有効かどうかを返してください。

「(」、「)」、「[」、「]」、「{」、「}」の6種類があります。次の場合に有効です。

カッコ

を1回開始する場合は、同じカッコで終了する必要があります.

カッコの順序は正しくなければなりません.

s = "()"
return true

s = "()[]{}"
return true

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

私の答え

def is_valid(string):
  if not string or len(string) == 1:
    return False
  
  a_dic = {"(": 1, "[": 1, "{": 1, ")": 0, "]": 0, "}": 0}
  b_dic = {")": "(", "}": "{", "]": "["}
  temp = []
  
  for index in range(len(string)):
    if index == 0 and a_dic[string[index]] == 0:
      return False
    
    if a_dic[string[index]] != 0:
      temp.append(string[index])
    else:
      if temp[-1] != b_dic[string[index]]:
        return False
      else:
        temp.pop()
  
  return True

カッコの開閉を判断できるディクシャナを作成します.

の開いたカッコに一致する閉じたカッコのキーと値のペアのディックシーケンスを作成します.

特定のカッコが開いている場合、そのカッコは配列tempに保存されます.

カッコが

で閉じたときにtempの最後の値である場合、pop()メソッドを使用してtempの最後の値を削除します.

4でカッコが閉じたときにtempの最後の値と異なる場合、falseが返されます.

まで最後にチェックしたが、エラーが返されなかった場合、Trueは有効カッコの配列を返すと判断できる.

に感銘を与える

この問題は何か解けないところがあるようで、1時間30分に決めました.
括弧が閉じられている場合は、次のような括弧を作成して、対応する括弧を検索することが望ましい.

  b_dic = {")": "(", "}": "{", "]": "["}

しかし、これは効率的なコードだとは思いません.

ソリューション

def is_valid(string):
    left = ['(', '{', '[']
    right = [')', '}', ']']
    stack = []
    for letter in string:
        if letter in left:
            stack.append(letter)
        elif letter in right:
            if len(stack) <= 0:
                return False
            if left.index(stack.pop()) != right.index(letter):
                return False
    return len(stack) == 0

私が書いた答えに比べて、カッコの開閉の判断はもっとスマートです.

はこれによりよりより可読性の高いコードとなり,変数名も明確になった.左の配列は開いた値で、右の配列は閉じた値です.

の値を開くコードと閉じるコードをチェックするのも簡単です.

スタックを使用します.