Pythonで文字列内の異なる整数の個数を求めるプログラム

問題概要

小文字の英数字から構成される文字列 s が与えられたとします。文字列中のすべての数字以外の文字を空白に置き換えると、少なくとも1つの空白で区切られた複数の整数が残ります。この置換操作を行った後、s に含まれる「異なる整数」の個数を求めるのが本問題です。

ここで、2つの数値が「異なる」とみなされる条件は、先頭のゼロを取り除いた10進表現が互いに異なることです。

具体例

入力が s = "ab12fg012th5er67" の場合、出力は 3 になります。理由を見てみましょう。

• 置換後の文字列には ["12", "012", "5", "67"] という4つの数値が含まれます。
• "12" と "012" は文字列としては別物ですが、先頭のゼロを除いた整数値として比較するとどちらも 12 であり同一です。

したがって、異なる整数は 12・5・67 の3個となり、答えは 3 になります。

解決のための手順

以下のアルゴリズムに従うことで効率的に解けます。

• 結果を格納するための空のリスト nums を用意する。
• 連続する数字を一時的に保持するための空文字列 k を用意する。
• i を 0 から s の長さまで順に走査する。
  • s[i] のASCIIコードが 47 より大きく 58 未満(つまり '0'〜'9' の数字)であれば、k に s[i] を連結する。
  • それ以外の場合、k が空文字列でなければ、k を整数に変換して nums の末尾に追加し、k を空文字列に戻す。
• ループ終了後も k が空文字列でなければ、その内容を整数化して nums に追加する(文字列末尾が数字で終わるケースへの対応)。
• nums 内の異なる要素の個数を返す。

Pythonによる実装例

def solve(s):
    nums = []
    k = ""
    for i in range(len(s)):
        if ord(s[i]) > 47 and ord(s[i]) < 58:
            k += s[i]
        else:
            if(k != ""):
                nums.append(int(k))
                k = ""
    if(k != ""):
        nums.append(int(k))
    return len(set(nums))
s = "ab12fg012th5er67"
print(solve(s))

入力

"ab12fg012th5er67"

出力

3

コードのポイント解説

• ord() による数字判定: 文字 '0'〜'9' のASCIIコードは 48〜57 であるため、「47より大きく58未満」という条件でその文字が数字かどうかを厳密に判定できます。
• int() による先頭ゼロの除去: 文字列 "012" を int("012") とすると 12 に変換されるため、先頭の余分なゼロが自動的に正規化されます。
• set() による重複排除: リスト nums を set に変換することで同じ値の整数が1つにまとめられ、len() で異なる整数の個数を簡単に取得できます。

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