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}
``