determine if a given pattern matches a string using backtracking pattern the pattern to match inputstring the string to match against the pattern return true if the pattern matches the string false otherwise matchwordpatternaba graphtreesgraph true matchwordpatternxyx pythonrubypython true matchwordpatterngg pythonjavapython false backtrack0 0 true backtrack0 1 true backtrack0 4 false 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 backtrack 0 0 true backtrack 0 1 true backtrack 0 4 false
def match_word_pattern(pattern: str, input_string: str) -> bool:
    

    def backtrack(pattern_index: int, str_index: int) -> bool:
        
        if pattern_index == len(pattern) and str_index == len(input_string):
            return True
        if pattern_index == len(pattern) or str_index == len(input_string):
            return False
        char = pattern[pattern_index]
        if char in pattern_map:
            mapped_str = pattern_map[char]
            if input_string.startswith(mapped_str, str_index):
                return backtrack(pattern_index + 1, str_index + len(mapped_str))
            else:
                return False
        for end in range(str_index + 1, len(input_string) + 1):
            substr = input_string[str_index:end]
            if substr in str_map:
                continue
            pattern_map[char] = substr
            str_map[substr] = char
            if backtrack(pattern_index + 1, end):
                return True
            del pattern_map[char]
            del str_map[substr]
        return False

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


if __name__ == "__main__":
    import doctest

    doctest.testmod()