Pythonでデコードされた文字列の指定インデックスの文字を効率的に求める方法

エンコードされた文字列 S が与えられたとします。この文字列を先頭から1文字ずつ読み込みながら、テープにデコード結果を書き出していきます。読み込んだ文字に応じて、以下の処理が行われます。

• 読み込んだ文字が英字の場合：その文字をそのままテープに書き込みます。
• 読み込んだ文字が数字の場合：現在のテープ全体を、その数字から1を引いた回数だけ追加で書き込みます（つまり、テープの内容がその数字倍になります）。

ここで、エンコードされた文字列 S とインデックス K が与えられたとき、デコード後の文字列における K 番目の文字（インデックスは1から開始）を見つけて返す必要があります。

例えば、文字列が「hello2World3」で k = 10 の場合、出力は「o」となります。これは、デコード後の文字列が「hellohelloWorldhellohelloWorldhellohelloWorld」になり、10番目の文字が「o」であるためです。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• size を 0 で初期化します。
• 文字列 s の各文字 i について前方向に走査します。
  • i が数字なら size := size × int(i)、それ以外なら size := size + 1 とします。これにより、デコード後の文字列の全長が求まります。
• 次に、文字列 s を末尾から先頭へ向かって逆順に走査します。
  • k := k mod size とします。
  • s[i] が英字で k = 0 の場合、s[i] を返します。
  • s[i] が英字なら size を 1 減らし、数字なら size := size / int(s[i]) とします。
• 該当する文字が見つからない場合は空文字列を返します。

この手法のポイントは、実際に巨大なデコード済み文字列を生成する必要がない点です。まずデコード後の総文字数 size を事前に計算しておき、末尾から逆算することで、K 番目の文字を効率的に特定できます。これにより、メモリ使用量と計算時間を大幅に削減でき、入力文字列が非常に長い場合でも高速に動作します。

実装例

class Solution(object):
    def decodeAtIndex(self, s, k):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        size = 0
        for i in s:
            if i.isdigit():
                size *= int(i)
            else:
                size += 1
        #print(size)
        for i in range(len(s) - 1, -1, -1):
            k %= size
            if s[i].isalpha() and k == 0:
                return s[i]
            if s[i].isalpha():
                size -=1
            else:
                size /= int(s[i])
        return ""
ob = Solution()
print(ob.decodeAtIndex("hello2World3", 10))

入力

"hello2World3"
10
ob.decodeAtIndex("hello2World3", 10)

出力

o