#LeetCode

LeetCode で「難易度: Easy」とされている Repeated Substring Pattern を解いた。与えられた文字列が「部分文字列を繰り返している文字列かどうか」を判定せよという問題だ。たとえば "abab" は "ab" を繰り返しているので true であり、"aba" は部分文字列を繰り返してできる文字列ではないので false である。

文字列の長さが 10^4 なので、部分文字列を繰り返しているのであれば、最長でも 10^4/2 の範囲を調べればよい。このくらいであれば確かにブルートフォースできそうなので、難易度は Easy でもよいかもしれない。

しかし、解答の Approach #2 Concatenation はずっと簡潔である。

僕はこれを理解するのに時間がかかった。未来の自分のために、これが何をしているのか書いてみよう。

(s + s)[1: -1] は与えられた文字列を二度繰り返して、そこから先頭と末尾の1文字を削ったものだ。つまり、"ab" が与えられたのであれば "abab" から先頭と末尾を削って "bab" である。これには "ab" が含まれているので true が返る。"aba が与えられたのであれば、(s + s)[1: -1] は "baab" であり、これは与えられた文字列を含まない。

なぜこれでうまく行くのか。与えられる文字列 s が部分文字列を繰り返したものであれば、s + s は最小でも部分文字列を 4 つ含むことになる。前後の1文字を削ることで、少なくとも 2 つの繰り返される部分文字列を持つことになる。それこそが与えられる文字列 s となる。

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]

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

LeetCode の Delete Nodes And Return Forest を Python 3 で解いてみた。 アルゴリズム 僕は木を探索しながら返り値を作り上げていくような実装をした。 具体的には、再帰関数 (walk_tree) に木の頂点を渡し、そこから子ノードがある限り自分自身をコールしていく。 再帰関数には has_parent という引数を設けて、親ノードがある場合とない場合で処理を分岐させる。親ノードがない場合 (i.e., has_parent = False の場合) はルートノードなので、返り値に自分自身を追加する。 木をたどる中で、ノードの値が to_delete に含まれる場合は has_parent = False として再帰関数をコールする。また 親を持たないノードはルート なので、そのノードは返り値のリストに append する。 コード 具体的なコードは次の通り。この実装で Runtime: 68 ms, faster than 66.80% of Python3 online submissions for Delete Nodes And Return Forest. とのこと。なお、同じ実装で faster than 85.44% of Python3 online submissions になることもあるので、多くの そこそこ速い 実装は似ているのだと思う。 ブログの読者向けに詳細にコメントを書き込んだコードを貼り付けておく。 from typing import List class TreeNode: def __init__(self, x): self. [Read More]

LeetCode の Decode String を Python 3 で解いてみた。 アルゴリズム tl;dr スタックを使って与えられた文字列をパースしながら、出力文字列を組み立てた。具体的には次の通りである。 与えられた文字列を左から走査する。[ を発見するたび、そこまでに現れた数字とアルファベットをスタックにプッシュする。] を見つけたらスタックから値をふたつポップして (それぞれ prev_num と prev_str という名前と仮定する) cur_str = prev_str + cur_str * int(prev_num) として文字列を組み立てる。ここでの右辺の cur_str は現時点までに現れたアルファベットである。 時間計算量は O(n) と言ってよいはず。与えられた文字列を走査 (O(n)) しながら処理 (O(1)) をするため。 具体的なコードは次の通り。この実装で Runtime: 24 ms, faster than 84.71% of Python3 online submissions for Decode String. とのこと。 #!/usr/bin/env python3 # -*- coding: utf-8 -*- # Difficulty: Medium # https://leetcode.com/problems/decode-string/ class Solution: def decodeString(self, string: str) -> str: stack = [] cur_num = '' cur_str = '' for char in string: # 入力文字は '[', ']', 数字, アルファベットの 4 パターンに分けて考える if char == '[': stack. [Read More]