LeetCode の Number of Matching Subsequences の解答例 (Python 3)
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.
[Read More]