Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment