LeetCode の Number of Matching Subsequences を Python 3 で解いてみた。説明の一部が Python 風の擬似コードになってしまったものの、雰囲気で読めるはず。

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

words を「先頭文字をキー、残りの文字列」をバリューとして辞書型のオブジェクトに保存する。問題文のサンプルである words = ["a", "bb", "acd", "ace"] の場合は、次の辞書オブジェクトを作る (以下 dic と呼ぶ)。

{
  'a': ['', 'cd', 'ce'],
  'b': ['b']
}

対応する S = "abcde" を走査しながら words 中の Subsequences を数えるにはどうすればよいだろうか。ひとつの案として dic を作り変えながら Subsequence を数え上げる方法がある。具体的には次のようにする。

  • 前準備として ans = 0 と初期化する (Subsequence を数え上げるために使う変数)
  • S[0] で dic を引くと ['', 'cd', 'ce'] というリストが返る (リストを取得後に dic[S[0]] をいったん削除する)
  • 取得したリストに含まれる文字列を順に調べていく (以下、リストに含まれるそれぞれの文字列を word と呼ぶ):
    • word が空文字であれば Subsequence を発見したことと等しいので ans += 1 する
    • word が空文字でなければ dic[word[0]] に word[1:] を追加する
  • S[1] で dic を引くと ['b'] というリストが返る (リストを取得後に dic[S[1]] をいったん削除する)
  • 取得したリストに含まれる文字列を順に調べていく (以下、リストに含まれるそれぞれの文字列を word と呼ぶ):
    • word が空文字であれば Subsequence を発見したことと等しいので ans += 1 する
    • word が空文字でなければ dic[word[0]] に word[1:] を追加する
  • S[2] で dic を引くと ['d', 'e'] というリストが返る (リストを取得後に dic[S[2]] をいったん削除する) … 以下略 (S[len(S)-1] まで同様の処理を繰り返す)

コード

次のようにコードを書いた。このコードは Runtime: 576 ms, faster than 61.49% of Python3 online submissions for Number of Matching Subsequences. と評価された。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Difficulty: Medium
# https://leetcode.com/problems/number-of-matching-subsequences/

from typing import List


class Solution:
    def numMatchingSubseq(self, S: str, words: List[str]) -> int:
        from collections import defaultdict

        # dic の構築
        dic = defaultdict(list)
        for word in words:
            dic[word[0]].append(word[1:])

        # 前準備
        ans = 0

        # S を走査しながら dic を作り変えていく
        for c in S:
            targets = dic[c]
            del(dic[c])

            for word in targets:
                if len(word) == 0:
                    # `word == ''` ということなので S の Subsequence を見つけたのと等価
                    ans += 1
                else:
                    dic[word[0]].append(word[1:])

        return ans


solution = Solution()
S = "abcde"
words = ["a", "bb", "acd", "ace"]
print(solution.numMatchingSubseq(S, words))  # 3