Pythonで文字列から等間隔の部分列として「programmingquestion」を検出する方法

問題概要

小文字のみで構成された文字列 s が与えられたとき、次の2つの条件を同時に満たす部分列（subsequence）が存在するかどうかを判定する問題を考えます。

• 選んだ文字たちの隣り合うインデックスの差がすべて等しい（等間隔に並んでいる）
• その文字をつなぎ合わせると「programmingquestion」という文字列になる

例えば、入力が「pzrzozgzrzazmzmziznzgzqzuzezsztzizozn」のような場合、適切な等間隔のステップで文字を拾うと「programmingquestion」が現れるため、出力は True となります。

解法のアプローチ

この問題は、開始位置となる「p」と2文字目の「r」の組み合わせを全探索することで解けます。具体的には以下の手順に従います。

• p：文字「p」が出現するインデックスの一覧を作成する
• r：文字「r」が出現するインデックスの一覧を作成する
• p の各インデックス j について、r の各インデックス k を調べる
  • k > j のとき、ステップ幅 k−j で切り出した部分文字列に「programmingquestion」が含まれていれば True を返す
• すべての組み合わせを試しても見つからなければ False を返す

ポイントは、最初の2文字「p」「r」の位置さえ決めれば、それ以降の文字は自動的に同じ間隔で並ぶことになる点です。したがって、p と r の位置の組み合わせだけを調べれば十分です。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
   def solve(self, s):
      p = [i for i, c in enumerate(s) if c == "p"]
      r = [i for i, c in enumerate(s) if c == "r"]
      for j in p:
         for k in r:
            if k > j:
               if "programmingquestion" in s[j:len(s):k-j]:
                  return True
      return False
ob = Solution()
s = "pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"
print(ob.solve(s))

入力

"pzrzozgzrzazmzmziznzgzqzuzezsztzizozn"

出力

True

コードの解説

まず、リスト内包表記を使って文字「p」と「r」の出現位置をそれぞれ抽出します。続いて、開始位置 j（「p」の位置）と2番目の位置 k（「r」の位置）のすべての組み合わせに対して、Pythonのスライス記法 s[j:len(s):k-j] を用いて、j 番目から k−j 間隔で文字を取り出した文字列を生成します。

この切り出した文字列の中に「programmingquestion」が連続して含まれていれば、元の文字列内に等間隔で並ぶ目的の部分列が存在することになります。計算量は、p と r の出現回数をそれぞれ P、R とすると O(P × R × N) 程度となり、多くのケースで実用的な速度で動作します。