Pythonで2つの文字列から辞書順に最小の文字列を作成するプログラム

問題の概要

2つの文字列が与えられたとき、それらを組み合わせて辞書順（字句順）で最小の文字列を作成することを考えます。作成の手順は次の通りです。

• まず2つの文字列の先頭の文字同士を比較します。
• 辞書順で小さい方の文字を取り出し、結果の文字列に追加します。
• 両方の文字が同じ場合（同点の場合）は、最初の文字列側から取り出します。
• この操作を両方の文字列が空になるまで繰り返し、構築された最小の文字列を返します。

具体例

入力が input_1 = 'TUTORIALS'、input_2 = 'POINT' の場合、出力は POINTTUTORIALS になります。

2つの文字列を比較すると、処理は次のように段階的に進みます。

TUTORIALS POINT
TUTORIALS OINT = P
TUTORIALS INT = PO
TUTORIALS NT = POI
TUTORIALS T = POIN
TUTORIALS = POINT

片方の文字列が空になった時点で、残った文字列全体がそのまま結果の文字列へ追加されます。したがって、最終的な文字列は POINTTUTORIALS となります。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

• input_1 の末尾に "z" を追加します。
• input_2 の末尾に "z" を追加します。
• temp_1 := 0 と初期化します。
• temp_2 := 0 と初期化します。
• res_str := 空文字列 とします。
• temp_1 < input_1 のサイズ かつ temp_2 < input_2 のサイズ の間、以下を繰り返します。
  • input_1[temp_1 以降] < input_2[temp_2 以降] の場合：
    • res_str := res_str + input_1[temp_1]
    • temp_1 := temp_1 + 1
  • そうでない場合：
    • res_str := res_str + input_2[temp_2]
    • temp_2 := temp_2 + 1
• res_str := res_str[先頭から末尾の2番目の要素まで]
• temp_1 < len(input_1) の場合：
  • res_str := res_str + input_1[temp_1 から末尾の2番目の要素まで]
• temp_2 < len(input_2) の場合：
  • res_str := res_str + input_2[temp_2 から末尾の2番目の要素まで]
• res_str を返します。

なぜ "z" を追加するのか

末尾に付ける "z" は番兵（センチネル）として機能します。"z" は英大文字よりも辞書順で大きいため、片方の文字列を使い切った状態では、その接尾辞（"z" のみ）は必ず相手の残りの接尾辞より大きくなります。その結果、もう一方の文字列の文字が自然に優先的に取り出され、特別な分岐処理を書かずに済みます。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(input_1, input_2):
    input_1 += "z"
    input_2 += "z"
    temp_1 = 0
    temp_2 = 0
    res_str = ""
    while temp_1 < len(input_1) and temp_2 < len(input_2):
        if input_1[temp_1:] < input_2[temp_2:]:
            res_str += input_1[temp_1]
            temp_1 += 1
        else:
            res_str += input_2[temp_2]
            temp_2 += 1
    res_str = res_str[:-1]
    if temp_1 < len(input_1):
        res_str += input_1[temp_1:-1]
    if temp_2 < len(input_2):
        res_str += input_2[temp_2:-1]
    return res_str

print(solve('TUTORIALS', 'POINT'))

入力

'TUTORIALS', 'POINT'

出力

POINTTUTORIALS

ポイントのまとめ

• 1文字だけを比較するのではなく、残りの接尾辞全体を比較することで、常に正しい貪欲な選択ができます。
• 番兵として "z" を追加することで、どちらかの文字列を使い切った場面の比較を自然に処理できます。
• 計算量は O((N+M)²) です（N、M はそれぞれの文字列の長さ）。ループが最大 N+M 回回り、各回で接尾辞の比較に最大 O(N+M) かかるためです。