# standard python backtracking solution, anyone know time complexity?

• ``````class Solution(object):
def wordPatternMatch(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
word_to_pat = {}
pat_to_word = {}

def match_util(s_idx, p_idx):
if s_idx == len(str) and p_idx == len(pattern):
return True

elif s_idx < len(str) and p_idx < len(pattern):
for i in xrange(s_idx, len(str)):
s_prefix = str[s_idx:i+1]
if s_prefix not in word_to_pat and pattern[p_idx] not in pat_to_word:
word_to_pat[s_prefix] = pattern[p_idx]
pat_to_word[pattern[p_idx]] = s_prefix

if match_util(i+1, p_idx + 1):
return True
else:
del word_to_pat[s_prefix]
del pat_to_word[pattern[p_idx]]

elif s_prefix in word_to_pat and pattern[p_idx] in pat_to_word:
if word_to_pat[s_prefix] == pattern[p_idx] and pat_to_word[pattern[p_idx]] == s_prefix:
return match_util(i+1, p_idx + 1)
else:
return False
return False

return match_util(0, 0)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.