ペアリング削除(Programmers 12973)

🧑‍💻 除去

ペアを削除するには、アルファベット小文字の文字列で開始します.まず、文字列内で同じ文字を2つ持つペアを検索します.次に、この2つの文字列を削除し、前後に文字列を接続します.

この手順を繰り返してすべての文字列を削除すると、ペアリングの削除が終了します.文字列Sが指定されている場合は、ペアリングを正常に削除できるかどうかを返す戻り関数を完了します.成功した場合は1を返し、そうでない場合は0を返します.例えば、文字列S=Baabaaの場合、

となる.

b aa baa → bb aa → aa →

の順序ですべての文字列を削除できるため、1を返します.

せいげんじょうけん

文字列長:100000以下の自然数

文字列はすべて小文字で構成されています.

I/O例
sresultbaabaa1cdcd0

🧑‍💻 解決策

スタックを使用し、ペアリングがない場合はすべて挿入し、

に失敗します.

スタックでペアを組む場合、pop処理は

を容易に解決することができる.

🧑‍💻 コード#コード#

def solution(s):
   stack = []

   for alpha in s :
       if len(stack) == 0 :
           stack.append(alpha)
       elif stack[-1] == alpha :
           stack.pop()
       else :
           stack.append(alpha)

   if len(stack) == 0 :
       return 1
   else :
       return 0

🧑‍💻 総評

パイソンニック号事故で全員死亡.

を覚えておいて、スタックに押すとpopで弾き出す方向を考えてみましょう!