# 291. Word Pattern II
Given a pattern and a string str, find if strfollows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Example 1:
Input: pattern = "abab", str = "redblueredblue"
Output: true
Example 2:
Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true
Example 3:
Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false
Notes: You may assume both pattern and str contains only lowercase letters.
# Solution
Approach 1: backtracking.
# Code (Python)
Approach 1:
def is_pattern(pattern, word):
# assuming bijection between 1 letter <> 1+ letter(s)
return _helper(pattern, word, 0, 0, {}, set())
def _helper(pattern, word, p_start, w_start, p2w, matched_words):
# p2w: pattern to word map
# matched_words: mapping the other way around, but only checking words don't duplicate
if p_start == len(pattern) and w_start == len(word):
return True
if p_start == len(pattern) or w_start >= len(word):
return False
for w_end in range(p_start, len(word)):
cur_pattern, cur_word = pattern[p_start], word[w_start:w_end + 1]
# if cur_word != p2w[cur_pattern], then continue
if cur_pattern in p2w and cur_word == p2w[cur_pattern]:
return _helper(pattern, word, p_start + 1, w_end + 1, p2w, matched_words)
# backtrack
if cur_pattern not in p2w:
if cur_word in matched_words:
continue
matched_words.add(cur_word)
p2w[cur_pattern] = cur_word
if _helper(pattern, word, p_start + 1, w_end + 1, p2w, matched_words):
return True
matched_words.remove(cur_word)
p2w.pop(cur_pattern)
return False
print(is_pattern("abab", "abab")) # true
print(is_pattern("abab", "redblueredblue")) # true
print(is_pattern("abab", "asdasdasdasd")) # true
print(is_pattern("aabb", "xyzabcxzyabc")) # false
print(is_pattern("abab", "aaaa")) # false
print(is_pattern("abab", "redredredred")) # true -- {a: r, b: edred}
``