match_word_pattern.py

defmatch_word_pattern(pattern: str, input_string: str) ->bool:
"""
 Determine if a given pattern matches a string using backtracking.

 pattern: The pattern to match.
 input_string: The string to match against the pattern.
 return: True if the pattern matches the string, False otherwise.

 >>> match_word_pattern("aba", "GraphTreesGraph")
 True

 >>> match_word_pattern("xyx", "PythonRubyPython")
 True

 >>> match_word_pattern("GG", "PythonJavaPython")
 False
 """

defbacktrack(pattern_index: int, str_index: int) ->bool:
"""
 >>> backtrack(0, 0)
 True

 >>> backtrack(0, 1)
 True

 >>> backtrack(0, 4)
 False
 """
ifpattern_index==len(pattern) andstr_index==len(input_string):
returnTrue
ifpattern_index==len(pattern) orstr_index==len(input_string):
returnFalse
char=pattern[pattern_index]
ifcharinpattern_map:
mapped_str=pattern_map[char]
ifinput_string.startswith(mapped_str, str_index):
returnbacktrack(pattern_index+1, str_index+len(mapped_str))
else:
returnFalse
forendinrange(str_index+1, len(input_string) +1):
substr=input_string[str_index:end]
ifsubstrinstr_map:
continue
pattern_map[char] =substr
str_map[substr] =char
ifbacktrack(pattern_index+1, end):
returnTrue
delpattern_map[char]
delstr_map[substr]
returnFalse

pattern_map: dict[str, str] = {}
str_map: dict[str, str] = {}
returnbacktrack(0, 0)


if__name__=="__main__":
importdoctest

doctest.testmod()