string - 检查给定的字符串是否遵循给定的模式

Question

我的一个 friend 刚刚在谷歌面试，被拒绝了，因为他无法给出这个问题的解决方案。

几天后我有自己的面试，似乎想不出办法解决。

问题是:

You are given a pattern, such as [a b a b]. You are also given a string, example "redblueredblue". I need to write a program that tells whether the string follows the given pattern or not.

A few examples:

Pattern: [a b b a] String: catdogdogcat returns 1

Pattern: [a b a b] String: redblueredblue returns 1

Pattern: [a b b a] String: redblueredblue returns 0

我想到了一些方法，比如获取模式中唯一字符的数量，然后找到字符串的许多唯一子字符串，然后使用 HashMap 与模式进行比较。但是，如果 a 的子字符串是 b 的一部分，那将是一个问题。

如果你们中有人能帮助我解决这个问题，那就太好了。 :)

更新:

新增信息:模式 (a-z) 中可以有任意数量的字符。两个字符不会代表相同的子字符串。此外，字符不能代表空字符串。

Answer 1

我能想到的最简单的解决方案是将给定的字符串分成四个部分并比较各个部分。您不知道 a 或 b 有多长，但是 a 和 b< 的长度相同 是。因此，如何划分给定字符串的方法数量不是很多。

例子: pattern = [a b a b], given string = redblueredblue (共14个字符)

1. |a|(a 的长度)= 1，则 a 有 2 个字符， 有 12 个字符code>bs，即 |b| = 6。分割字符串 = r edblue r edblue。哇，这马上就匹配了!
2. (出于好奇)|a| = 2, |b| = 5 -> 分割字符串 = re dblue re dblue -> 匹配

示例 2: pattern = [a b a b], string = redbluebluered (共14个字符)

1. |a| = 1, |b| = 6 -> 分割字符串 = r edblue bluered -> 不匹配
2. |a| = 2, |b| = 5 -> 分割字符串 = re dblue bluered -> 不匹配
3. |a| = 3, |b| = 4 -> 分割字符串 = red blue blu ered -> 不匹配

其余的不需要检查，因为如果将 a 切换为 b，反之亦然，情况是相同的。

具有 [a b c a b c] 的模式是什么？