Check if the given string follows the given pattern

Question

A friend of mine just had his interview at Google and got rejected because he couldn't give a solution to this question.

I have my own interview in a couple of days and can't seem to figure out a way to solve it.

Here's the question:

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

I thought of a few approaches, like getting the number of unique characters in the pattern and then finding that many unique substrings of the string then comparing with the pattern using a hashmap. However, that turns out to be a problem if the substring of a is a part of b.

It'd be really great if any of you could help me out with it. :)

UPDATE:

Added Info: There can be any number of characters in the pattern (a-z). Two characters won't represent the same substring. Also, a character can't represent an empty string.

Answer 1

The simplest solution that I can think of is to divide the given string into four parts and compare the individual parts. You don't know how long a or b is, but both as are of the same length as well as bs are. So the number of ways how to divide the given string is not very large.

Example: pattern = [a b a b], given string = redblueredblue (14 characters in total)

1. |a| (length of a) = 1, then that makes 2 characters for as and 12 characters is left for bs, i.e. |b| = 6. Divided string = r edblue r edblue. Whoa, this matches right away!
2. (just out of curiosity) |a| = 2, |b| = 5 -> divided string = re dblue re dblue -> match

Example 2: pattern = [a b a b], string = redbluebluered (14 characters in total)

1. |a| = 1, |b| = 6 -> divided string = r edblue b luered -> no match
2. |a| = 2, |b| = 5 -> divided string = re dblue bl uered -> no match
3. |a| = 3, |b| = 4 -> divided string = red blue blu ered -> no match

The rest is not needed to be checked because if you switched a for b and vice versa, the situation is identical.

What is the pattern that has [a b c a b c] ?

Answer 2

Don't you just need to translate the pattern to a regexp using backreferences, i.e. something like this (Python 3 with the "re" module loaded):

>>> print(re.match('(.+)(.+)\\2\\1', 'catdogdogcat'))
<_sre.SRE_Match object; span=(0, 12), match='catdogdogcat'>

>>> print(re.match('(.+)(.+)\\1\\2', 'redblueredblue'))
<_sre.SRE_Match object; span=(0, 14), match='redblueredblue'>

>>> print(re.match('(.+)(.+)\\2\\1', 'redblueredblue'))
None

The regexp looks pretty trivial to generate. If you need to support more than 9 backrefs, you can use named groups - see the Python regexp docs.