patterns.py

def wordpattern(pattern, string):
    unique_types = {}
    for c in list(pattern):
        unique_types[c] = 1

    patterns = sorted(unique_types.keys())
    return wordpattern_helper(0, patterns, {}, pattern, string)

def wordpattern_helper(start, patterns, memo, final_pattern, string):
    if len(patterns) == 0:
        return False

    new_patterns = list(patterns)
    pattern = new_patterns.pop(0)

    for i in range(start, len(string)):
        attempt_str = string[start:i+1]
        new_memo = dict(memo)
        new_memo[pattern] = attempt_str
        if len(new_patterns) == 0 and check_pattern(new_memo, final_pattern, string):
            return True

        if wordpattern_helper(i+1, new_patterns, new_memo, final_pattern, string):
            return True

    return False

def check_pattern(memo, final_pattern, string):
    print "testing: ", memo, final_pattern, string
    i = 0
    tests = list(final_pattern)
    while i < len(string):
        if len(tests) == 0:
            return False

        p = tests.pop(0)

        if p not in memo:
            return False

        p_string = memo[p]

        if p_string != string[i:i+len(p_string)]:
            return False

        i += len(p_string)

    return len(tests) == 0

assert wordpattern("aaaa", "redredredred") == True
assert wordpattern("abba", "redbluebluered") == True
assert wordpattern("aaaa", "redbluebluered") == False
assert wordpattern("abcba", "redblueyellowbluered") == True
assert wordpattern("abba", "redredredred") == True
assert wordpattern("abba", "abcxyzxyzabc") == True
assert wordpattern("ab", "redblueredblue") == True
assert wordpattern("abc", "abc") == True
assert wordpattern("abcd", "thequickbrownfox") == True