Pythonで解く「古代宇宙飛行士の辞書」問題 ― 文字列が独自の辞書順に並んでいるか判定する

今回は、「古代宇宙飛行士の辞書（astro_dict）」と呼ばれる独自の文字順序に基づき、与えられた文字列 s がその辞書順に従って正しく並んでいるかどうかを判定する方法を解説します。

ここでの辞書は、特定の文字集合に関する部分的な辞書順序を表しています。つまり、辞書に含まれていない文字（空白や記号など）は順序の判定対象外となり、単純に読み飛ばされます。

入力例と期待される出力

たとえば、dictionary = "bdc"、s = "bbbb h ddd i cccc" という入力が与えられた場合、出力は True になります。

これは、辞書内に存在する文字だけに着目すると、すべての「b」が「d」より先に現れ、すべての「d」が「c」より先に現れているためです。「h」や「i」は辞書に存在しないため、順序のチェックから除外されます。

解法のアプローチ

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

• まず、変数 l に astro_dict の長さを代入します。
• l が 0（空の辞書）の場合は、順序の制約が存在しないため True を返します。
• ポインタ i を 0 で初期化します。
• 文字列 s 内の各文字 c について、以下を繰り返します。
  • c が astro_dict に含まれる場合：
    • i < l かつ astro_dict[i] が c と異なる間、i を 1 ずつ進めます。
    • ループ終了後、i >= l（辞書の末尾を超えた）または astro_dict[i] が c と一致しない場合は、順序違反なので False を返します。
• すべての文字を処理して問題がなければ、True を返します。

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

実装例

class Solution:
   def solve(self, astro_dict, s):
      l = len(astro_dict)
      if l == 0:
         return True
      i = 0
      for c in s:
         if c in astro_dict:
            while i < l and astro_dict[i] != c:
               i += 1
            if i >= l or astro_dict[i] != c:
               return False
      return True
ob = Solution()
print(ob.solve("bdc","bbbb h ddd i cccc"))

入力

"bdc","bbbb h ddd i cccc"

出力

True

アルゴリズムのポイント

このアルゴリズムの核心は、ポインタ i が常に前方にしか進まないという点です。これにより、一度通過した位置より前の文字が再び出現した場合（＝辞書順に反する並び）を自動的に検出できます。

文字列 s の長さを n、辞書の長さを m とすると、時間計算量は O(n + m)、追加で必要なメモリは O(1) に抑えられるため、非常に効率的な手法といえます。独自の順序定義を持つデータのバリデーションなど、実務でも応用範囲の広いパターンですので、ぜひマスターしておきましょう。