Pythonで丸括弧で囲まれた部分文字列を再帰的に反転するプログラム

問題概要

小文字の英字と丸括弧「(」「)」を含む文字列 s が与えられます。このとき、括弧で囲まれた部分文字列を再帰的に反転し、最終的な文字列を返すプログラムを作成します。

たとえば、入力が s = "back(aps)ce" の場合、括弧内の「aps」が反転されて「spa」になり、出力は「backspace」となります。

解法の考え方

この問題は、次の2つの処理に分けて考えるのがポイントです。

• 前処理：スタックを使い、開き括弧「(」と閉じ括弧「)」のペアとなるインデックス同士を事前に記録します。
• 走査：進行方向 dir（+1 または -1）を持ちながら文字列を走査する trav() 関数を定義します。括弧に到達したら、そのペアの位置へジャンプし、方向を反転させて再帰的に処理を続けます。

手順の詳細

まず、trav() 関数を定義します。引数は s（対象の文字列）、dir（走査の方向）、start（開始位置）、close（括弧の対応表）、ans（結果を格納するリスト）です。

1. end を決めます。dir が -1（逆方向）なら「(」、それ以外なら「)」です。
2. other を決めます。end が「)」なら「(」、そうでなければ「)」です。
3. start が文字列長未満 かつ s[start] が end と異なる間、次を繰り返します。
   • s[start] が other と一致する場合：
     • trav(s, -dir, close[other][start] - dir) を呼び出し、対応する括弧の内側へジャンプします。
     • start を close[other][start] + dir に更新します。
   • それ以外の場合：
     • s[start] を ans の末尾に追加します。
     • start を dir 分だけ進めます。

続いて、メイン処理では以下を行います。

1. ans：結果を格納する空のリストを用意します。
2. close：「)」と「(」をキーに持つ辞書を用意します。値はそれぞれ空の辞書で、ここに括弧の対応関係を記録します。
3. stack：スタックとして使う空のリストを用意します。
4. 文字列 s の各インデックス i と各文字 c について次を判定します。
   • c が「(」のとき：インデックス i をスタックにプッシュします。
   • c が「)」のとき：スタックから先頭をポップして o とし、close[")"][i] = o および close["("][o] = i を記録します。
5. trav(s, 1, 0) を呼び出して先頭から走査を開始します。
6. ans を空文字で連結した結果を返します。

実装例

class Solution:
   def solve(self, s):
      ans = []
      close = {")": {}, "(": {}}
      stack = []
      for i, c in enumerate(s):
         if c == "(":
            stack.append(i)
         elif c == ")":
            o = stack.pop()
            close[")"][i] = o
            close["("][o] = i
      def trav(s, dir, start, close=close, ans=ans):
         end = "(" if dir == -1 else ")"
         other = "(" if end == ")" else ")"
         while start < len(s) and s[start] != end:
            if s[start] == other:
               trav(s, -dir, close[other][start] - dir)
               start = close[other][start] + dir
            else:
               ans.append(s[start])
               start += dir
      trav(s, 1, 0)
      return "".join(ans)
ob = Solution()
print(ob.solve("back(aps)ce"))

入力

"back(aps)ce"

出力

backspace

動作の流れ

入力「back(aps)ce」の場合、処理は次のように進みます。

1. 前処理により、インデックス4の「(」とインデックス8の「)」がペアとして記録されます。
2. trav() が dir=+1 で開始し、「b」「a」「c」「k」を順に ans へ追加します。
3. インデックス4の「(」に到達すると、ペアの位置へジャンプし、dir=-1 でインデックス7から逆方向に走査。「s」「p」「a」の順に追加されます。
4. 再び「(」に到達した時点で呼び出し元に戻り、閉じ括弧の直後（インデックス9）から dir=+1 で走査を再開。「c」「e」を追加します。
5. 最終的に ans は「b, a, c, k, s, p, a, c, e」となり、連結すると「backspace」が出力されます。