Word Pattern II - Backtracking / Additional Practices


Below is a python solution for the above problem:

from typing import List, Dict, Set
def word_pattern_match(pattern: str, s: str) → bool:
# Special cases
if len(pattern) == 0 and len(s) == 0:
return True

if len(pattern) == 0:
    return False

def dfs(pattern: str, s: str, pattern_index: int, str_index: int, 
        mapper: Dict[str, str], tracker: Set[str]):
    if pattern_index == len(pattern) and str_index == len(s):
        return True
    if pattern_index >= len(pattern) or str_index >= len(s):
        return False
    character = pattern[pattern_index]
    for stop_index in range(str_index+1, len(s)+1):
        substr = s[str_index:stop_index]
        if character not in mapper and substr not in tracker:
            mapper[character] = substr
            if dfs(pattern, s, pattern_index+1, stop_index, mapper, tracker):
                return True
        elif character in mapper and mapper.get(character) == substr:
            if dfs(pattern, s, pattern_index+1,stop_index, mapper, tracker):
                return True
    return False

mapper = {}
tracker = set([])
return dfs(pattern, s, 0, 0, mapper, tracker)

if name == ‘main’:
pattern = input()
s = input()
res = word_pattern_match(pattern, s)
print(‘true’ if res else ‘false’)

What’s need of creating HashSet in here?