'a'と'b'でパターンマッチ
問題
文字列wordとパターンを表すpatternが入力値として与えれる。patternは'a'と'b'のみで構成されている。wordがpatternにマッチするか否かを求める問題。
例
word = “catcatgocatgo”, pattern = “abbab”
a -> cat
b -> go
とすればwordはpatternにマッチすることができるのでtrueを返す。
解法
wordの先頭から１文字ずつaに変換する。
a -> c
a -> ca
a -> cat
といった具合だ。aが決まるとbが決定する。これは、pattern = “abbab"の中のaとbそれぞれの出現回数とwordのlengthによって求めることができる。aとbが決定したらpatternにそって文字列を生成し、wordと一致するかをチェックしてあげれば良い。
計算量
wordのサイズをNとすると、aを決定するためにO(N)。bはO(1)で決定し、aとbの部分文字列を生成するための処理と、patternを元に候補となる文字列を生成し比較する処理がそれぞれO(N)(これらはネストではない)ので空間計算量はO(N2)となる。
