'a'と'b'でパターンマッチ

問題

文字列wordとパターンを表すpatternが入力値として与えれる。patternは'a'と'b'のみで構成されている。wordがpatternにマッチするか否かを求める問題。

word = “catcatgocatgo”, pattern = “abbab”
a -> cat
b -> go
とすればwordはpatternにマッチすることができるのでtrueを返す。

解法

wordの先頭から1文字ずつaに変換する。

a -> c

a -> ca

a -> cat

といった具合だ。aが決まるとbが決定する。これは、pattern = “abbab"の中のabそれぞれの出現回数とwordのlengthによって求めることができる。aとbが決定したらpatternにそって文字列を生成し、wordと一致するかをチェックしてあげれば良い。

計算量

wordのサイズをNとすると、aを決定するためにO(N)。bはO(1)で決定し、aとbの部分文字列を生成するための処理と、patternを元に候補となる文字列を生成し比較する処理がそれぞれO(N)(これらはネストではない)ので空間計算量はO(N2)となる。

ソースコード