Pythonでバイナリ文字列内のすべての「1」が等間隔に並んでいるか判定する方法

バイナリ文字列 s が与えられたとき、文字列中のすべての「1」が等間隔（等距離）に配置されているかどうかを判定する問題です。言い換えると、隣接する任意の2つの「1」の間の距離がすべて同じである必要があります。なお、文字列には少なくとも2つの「1」が含まれているものとします。

たとえば、入力が s = "100001000010000" の場合、「1」同士の間隔はいずれも4で一定であるため、出力は True になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 「1」が出現する位置（インデックス）を格納するための新しいリスト index を用意します。
• i を 0 から文字列 s の長さまで順に走査し、s[i] が '1' であれば、その位置 i をリスト index の末尾に追加します。
• 変数 t にリスト index のサイズを代入します。
• i を 1 から t - 1 まで繰り返し、(index[i] - index[i - 1]) が最初の間隔 (index[1] - index[0]) と一致しない場合は False を返します。
• ループが最後まで完了すれば、すべての間隔が等しいことになるため True を返します。

それでは、理解を深めるために実際の実装例を見てみましょう。

実装例

def solve(s):
    index = []
    for i in range(len(s)):
        if s[i] == '1':
            index.append(i)
    t = len(index)
    for i in range(1, t):
        if (index[i] - index[i - 1]) != (index[1] - index[0]):
            return False
    return True

s = "100001000010000"
print(solve(s))

入力

"100001000010000"

出力

True

計算量について

このアルゴリズムでは、まず文字列を一度走査して「1」の位置を収集するのに O(n) の時間がかかり、その後の間隔チェックでも最大 O(n) の処理が必要です。したがって、全体の時間計算量は O(n) となり、空間計算量も「1」の位置を保存するリストの分だけ O(n) となります（n は文字列の長さ）。文字列を1回の走査で済ませるシンプルかつ効率的なアプローチと言えます。