<commit_before># Time:  O(n * C(n + c - 1, c - 1)), n is length of str, c is unique count of pattern,
#                                    there are C(n + c - 1, c - 1) possible splits of string,
#                                    and each one costs O(n) to check if if matches the word pattern.
# Space: O(n + c)

class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        w2p, p2w = {}, {}
        return self.match(pattern, str, 0, 0, w2p, p2w)


    def match(self, pattern, str, i, j, w2p, p2w):
        is_match = False
        if i == len(pattern) and j == len(str):
            is_match = True
        elif i < len(pattern) and j < len(str):
            p = pattern[i]
            if p in p2w:
                if p2w[p] == str[j:j+len(p2w[p])]:  # Match pattern.
                    is_match = self.match(pattern, str, i + 1, j + len(p2w[p]), w2p, p2w)
                # Else return false.
            else:
                for k in xrange(j, len(str)):
                    w = str[j:k+1]
                    if w not in w2p:
                        # Build mapping. Space: O(n + c)
                        w2p[w], p2w[p] = p, w;
                        is_match = self.match(pattern, str, i + 1, k + 1, w2p, p2w)
                        w2p.pop(w), p2w.pop(p);
                    if is_match:
                        break
                    # Else try longer word.
        return is_match

<commit_msg>Update word-pattern-ii.py<commit_after># Time:  O(n * C(n + c - 1, c - 1)), n is length of str, c is unique count of pattern,
#                                    there are C(n + c - 1, c - 1) possible splits of string,
#                                    and each one costs O(n) to check if if matches the word pattern.
# Space: O(n + c)

class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        w2p, p2w = {}, {}
        return self.match(pattern, str, 0, 0, w2p, p2w)


    def match(self, pattern, str, i, j, w2p, p2w):
        is_match = False
        if i == len(pattern) and j == len(str):
            is_match = True
        elif i < len(pattern) and j < len(str):
            p = pattern[i]
            if p in p2w:
                w = p2w[p]
                if w == str[j:j+len(w)]:  # Match pattern.
                    is_match = self.match(pattern, str, i + 1, j + len(w), w2p, p2w)
                # Else return false.
            else:
                for k in xrange(j, len(str)):
                    w = str[j:k+1]
                    if w not in w2p:
                        # Build mapping. Space: O(n + c)
                        w2p[w], p2w[p] = p, w;
                        is_match = self.match(pattern, str, i + 1, k + 1, w2p, p2w)
                        w2p.pop(w), p2w.pop(p);
                    if is_match:
                        break
                    # Else try longer word.
        return is_match


{'fraction_non_alphanumeric': 0.11738002594033722, 'fraction_numerical': 0.018158236057068743, 'mean_word_length': 1.1755994358251058, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4088079', 'n_tokens_mistral': 1030, 'n_tokens_neox': 969, 'n_words': 319}