Pythonで数字列を英小文字に復号化するアルゴリズムを解説

問題の概要

数字（'0'〜'9'）と '#' で構成される文字列 s が与えられます。この文字列を、以下のルールに従って英語の小文字アルファベットへと復号化します。

• 文字 'a' 〜 'i' は、それぞれ '1' 〜 '9' に対応します。
• 文字 'j' 〜 'z' は、それぞれ '10#' 〜 '26#' に対応します。

例えば、入力が「10#11#12」の場合、出力は「jkab」となります。「10#」が j、「11#」が k、「1」が a、「2」が b に対応するためです。なお、常に一意なマッピングが存在すると仮定してよいものとします。

解法のアプローチ

この問題は、文字列を後ろから走査することで効率的に解けます。手順は以下の通りです。

1. '1'〜'26' の各数値と対応するアルファベットを格納したマップ（辞書）を作成します。
2. 結果を格納する変数 ans を空文字列で初期化し、インデックス i を文字列の末尾（長さ − 1）に設定します。
3. i が 0 以上である限り、以下を繰り返します。
   • s[i] が '#' の場合：直前の2文字と合わせた3文字（例：「10#」）を取り出し、マップで対応する文字に変換して ans の先頭に追加します。その後、i を 3 減らします。
   • それ以外の場合：s[i] の1文字をマップで変換し、ans の先頭に追加します。i を 1 減らします。
4. 最終的な ans を返します。

後ろから処理する理由は、'#' に出会った時点で、その直前の2桁の数字とセットで判断できるからです。これにより、1桁の数字と2桁の数字を正しく区別できます。

Pythonでの実装例

以下の実装を見ると、より理解が深まります。

class Solution(object):
    def freqAlphabets(self, s):
        m = {}
        x = 'a'
        for i in range(1, 27):
            m[str(i)] = x
            x = chr(ord(x) + 1)
        ans = ""
        m[''] = ''
        i = len(s) - 1
        while i >= 0:
            if s[i] == "#":
                temp = ""
                for j in range(i - 2, i):
                    temp += s[j]
                ans = m[str(temp)] + ans
                i -= 3
            else:
                ans = m[s[i]] + ans
                i -= 1
        return ans

ob1 = Solution()
print(ob1.freqAlphabets("17#123#5621#"))

入力

"17#123#5621#"

出力

qawefu

コードの解説

まず、for ループを使って '1' から '26' までの数値をキーとし、対応するアルファベットを値とする辞書 m を作成しています。chr() 関数と ord() 関数を組み合わせることで、'a' から順に1文字ずつずらしながらアルファベットを自動的に生成できます。

その後、文字列の末尾から走査を行います。現在位置の文字が '#' であれば、その前の2文字を含めた3文字分（例：「17#」）をひとつのキーとして扱い、対応する文字を結果に追加します。'#' がない場合は、その1文字だけをキーとして変換します。

この実装の計算量は O(n) です。文字列を一度だけ走査すればよいため、非常に効率的な手法と言えます。