LeetCode の Shortest Way to Form String を Python 3 で解いてみた。なお、基本的なアイディアは Twoho さんの Discussion へのポスト を参考にしている。

直感的なアイディアの説明

次の入力を考えてみよう。

  • source: "abcab"
  • target: "aabbaac"

まず source から、次のデータ構造を作り出す。

{
  'a': [0, 3],
  'b': [1, 4],
  'c': [2]
}

これは「キーがアルファベット、値が出現位置のリスト」な辞書である。

次に具体的な処理について考えよう。まず source のどこに注目しているかを示すインデックスを i とする (初期値: 0)。また source を何巡したか示す変数を cnt_loop とする (初期値: 1)。cnt_loop が最終的な解となる。なぜなら、source を巡回する数が minimum number of subsequences そのものになるからである。

ここまでを前準備として、target を走査しながら次の処理をしていく。target 中で注目している文字を c とする。

  1. 最初の c は target[0] すなわち 'a' である。これで辞書を引くと [0, 3] である。このリストで i 以上の最小の値 は 0 なのでインデックスをひとつ進めて (0 + 1 して) i = 1 とする。
  2. 次の c は target[1] すなわち a である。これで辞書を引くと [0, 3] である。このリストで i 以上の最小の値 は 3 なのでインデックスをひとつ進めて (3 + 1 して) i = 4 とする。
  3. 次の c は target[2] すなわち b である。これで辞書を引くと [1, 4] である。このリストで i 以上の最小の値 は 4 なのでインデックスをひとつ進めて (4 + 1 して) i = 5 とする。
  4. 次の c は target[3] すなわち b である。これで辞書を引くと [1, 4] である。このリストで i 以上の最小の値 は存在しないので、cnt_loop += 1 しつつ i をリストの最小の要素 + 1 (つまり 1 + 1 = 2) にする。
  5. 次の c は target[4] すなわち b である。これで辞書を引くと [1, 4] である。このリストで i 以上の最小の値 は 4 なのでインデックスをひとつ進めて (4 + 1 して) i = 5 とする。
  6. … (省略) …

このようにしていくと、最終的に cnt_loop は 3 となる。

コード

次のようにコードを書いた。このコードは Runtime: 32 ms, faster than 90.20% of Python3 online submissions for Shortest Way to Form String. と評価された。

class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        from collections import defaultdict
        from bisect import bisect_left

        # source の各文字と出現位置をマップする辞書の作成
        source_dic = defaultdict(list)
        for i, c in enumerate(source):
            source_dic[c].append(i)

        # 前準備
        loop_cnt = 1
        i = 0

        # target を走査する間に source を何巡するか数える
        for c in target:
            positions = source_dic[c]

            # source に存在しない文字が target に存在するなら、
            # source は target の subsequence ではないので -1 を返す
            if len(positions) == 0:
                return -1

            bisect_result = bisect_left(positions, i)

            # bisect_left は第二引数を挿入できる位置を発見できる場所を見つけられないとき、
            # 第一引数の len() を取ったものと同じ値を返す
            if bisect_result == len(positions):
                loop_cnt += 1
                i = positions[0] + 1
            else:
                i = positions[bisect_result] + 1

        return loop_cnt