standard python backtracking solution, anyone know time complexity?


  • 0
    I
    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)
    

Log in to reply
 

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