私の友人は先日 Google の面接を受けたのですが、この質問に対する答えが提示できなかったため不採用になりました。
数日後に自分の面接があるのですが、解決方法がわかりません。
質問は次のとおりです:
[abab] のようなパターンが与えられます。また、"redblueredblue" のような文字列も与えられます。文字列が与えられたパターンに従っているかどうかを判定するプログラムを作成する必要があります。
いくつかの例:
パターン: [abba] 文字列: catdogdogcat は 1 を返します
パターン: [abab] 文字列: redblueredblue は 1 を返します
パターン: [abba] 文字列: redblueredblue は 0 を返します
パターン内の一意の文字数を取得し、その数の文字列の一意の部分文字列を見つけて、ハッシュマップを使用してパターンと比較するなど、いくつかのアプローチを考えました。ただし、a の部分文字列が b の一部である場合は問題になります。
どなたか助けていただけると本当に嬉しいです。:)
アップデート：
追加情報: パターンには任意の数の文字を含めることができます (az)。2 つの文字は同じ部分文字列を表すことはできません。また、文字は空の文字列を表すことはできません。
ベストアンサー1
私が思いつく最も簡単な解決法は、与えられた文字列を 4 つの部分に分割し、個々の部分を比較することです。aまたは の長さbはわかりませんが、 は両方aとも同じ長さであり、 もb同じです。したがって、与えられた文字列を分割する方法の数はそれほど多くありません。
例: パターン = [a b a b]、指定された文字列 = redblueredblue(合計 14 文字)
|a|( の長さa) = 1 の場合、 s の文字数は 2 になり、 saの残り文字数は 12 文字、つまり= 6 になります。分割された文字列 = 。おお、これはすぐに一致します!b|b|r edblue r edblue- (単なる好奇心から)
|a| = 2, |b| = 5-> 分割された文字列 =re dblue re dblue-> 一致
例 2: パターン = [a b a b]、文字列 = redbluebluered(合計 14 文字)
|a| = 1, |b| = 6-> 分割された文字列 =r edblue b luered-> 一致なし|a| = 2, |b| = 5-> 分割された文字列 =re dblue bl uered-> 一致なし|a| = 3, |b| = 4-> 分割された文字列 =red blue blu ered-> 一致なし
残りは、aに切り替えた場合bやその逆の場合も状況は同じなので、確認する必要はありません。
[abcabc] というパターンは何ですか?