My solution to coding problem: write a function that determines if a string matches a pattern where pattern is expressed as a string of characters.

wordpattern.py

recursions = 0
words_at_position = {}

def matches_pattern(pattern, input, start, pattern_map):
    global recursions

    recursions = recursions + 1 if start else 0

    # empty pattern or end of input that we've gone as
    # far as possible. If both are true: jackpot
    at_end = start == len(input)
    empty_pattern = not pattern
    if at_end or empty_pattern:
        if at_end and empty_pattern:
            return pattern_map
        return False

    key = pattern[:1]
    if key in pattern_map:
        if pattern_map[key] in words_at_position[start]:
            # bingo. keep going to end
            return matches_pattern(
                pattern[1:], 
                input, 
                start+len(pattern_map[key]), 
                pattern_map)
        else:
            return False
    else:
        for word in words_at_position[start]:
            recurse_dict = dict(pattern_map)
            recurse_dict[key] = word
            matched_dict = matches_pattern(
                    pattern[1:], 
                    input, 
                    start+len(word), 
                    recurse_dict)
            if matched_dict:
                return matched_dict
            else:
                continue # not necessary but for clarity
    return False


def wordpattern(pattern,  input):
    global words_at_position
    # build list of possible words at each position in input
    for start in range(len(input)):
        words_at_position[start] = []
        # reverse so that words are towards front of list (vs letters)
        for end in reversed(range(start, len(input))):
            words_at_position[start].append(input[start:end+1])

    matched_patterns = matches_pattern(pattern, input, 0, {})

    print recursions
    # if match found, print match 
    if matched_patterns:
        matched = ''.join([matched_patterns[k] for k in pattern])
        print matched
        return True
    return False


assert wordpattern('azaa', 'redblueredred')
assert not wordpattern('azaa', 'redblueredredgreen')
assert wordpattern('a', 'b')
assert not wordpattern('aaz', 'redblueredred')
assert wordpattern('tqbfjotld','thequickbrownfoxjumpsoverthelazydog')
assert wordpattern('tsqsbsfsjsostslsd','the quick brown fox jumps over the lazy dog')
assert not wordpattern('aaaa', 'b')

Would be cleaner as a class but this is super fast.