連結するとターゲットと一致する、ソース部分列の最小個数を求めるPythonプログラム

2つの文字列 source(ソース)と target(ターゲット)が与えられます。source の部分列を何度でも切り出して連結し、target とまったく同じ文字列を作りたいとき、必要となる部分列の最小個数を求めます。どのように組み合わせても target を作れない場合は -1 を返します。

たとえば source = "xyz"、target = "xyzyzz" の場合、答えは 3 になります。"xyz" + "yz" + "z" のように3つの部分列を連結すると target と一致するからです。

解法のアプローチ(貪欲法)

この問題は貪欲法で効率的に解けます。target を先頭から順に走査し、source を一度なぞるごとに「できるだけ多くの文字」をマッチさせます。source を使い切った時点で連結回数を1つ増やし、target の続きから再び source の先頭へ戻ってマッチングを続けます。もし1周で1文字もマッチできなければ、target を構成することが不可能なので -1 を返します。

手順をまとめると次のようになります。

• s_size := s の長さ、t_size := t の長さとする
• concat_count := 0(連結回数)、target_idx := 0(target の走査位置)で初期化する
• target_idx < t_size の間、以下を繰り返す
  • source_idx := 0 とし、source の走査位置をリセットする
  • temp_index := target_idx として現在の進捗を記録する
  • source_idx < s_size かつ target_idx < t_size の間、以下を繰り返す
    • s[source_idx] と t[target_idx] が一致していれば target_idx を1進める
    • source_idx を1進める
  • temp_index と target_idx が等しい場合(1文字もマッチしなかった場合)は -1 を返す
  • concat_count を1増やす
• 最後に concat_count を返す

Pythonでの実装例

以下のコードで実際の動きを確認できます。

class Solution:
    def solve(self, s, t):
        s_size, t_size = len(s), len(t)
        concat_count = 0
        target_idx = 0
        while target_idx < t_size:
            source_idx = 0
            temp_index = target_idx

            while source_idx < s_size and target_idx < t_size:
                if s[source_idx] == t[target_idx]:
                    target_idx += 1
                source_idx += 1

            if temp_index == target_idx:
                return -1
            concat_count += 1
        return concat_count

ob = Solution()
source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))

入力

"xyz", "xyzyzz"

出力

3

計算量の目安

時間計算量は O(t_size × s_size) です。外側のループは最大 t_size 回(target は1周ごとに少なくとも1文字進むため)、内側のループは最大 s_size 回走査するためです。空間計算量は O(1) で、追加のデータ構造は一切不要です。

貪欲法が正しく機能するのは、「1周でできるだけ遠くまで進む」という戦略が常に連結回数を最小化する方向に働くためです。target の各文字を無駄なく消費できるため、このシンプルなアプローチで最適解が得られます。