Word Pattern II

Problem: Word Pattern II

The solution is complicate while the general idea is simple. We do backtracking on the word and pattern and record the relations in a dictionary. We first check whether there's a word start at current position match the stored pattern. If not, we try to add new pattern by backtracking.

Code in Python:

class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        def helper(dict, p, pos):
            if p == len(pattern) and pos == len(str): return True
            elif p == len(pattern): return False
            elif pos == len(str): return False
            letter = pattern[p]
            if letter in dict:
                if pos+len(dict[letter])<=len(str) and dict[letter] == str[pos:pos+len(dict[letter])]:
                    if helper(dict, p+1, pos+len(dict[letter])): return True
                    else: return False
                else:
                    return False
            for i in xrange(pos+1, len(str)+1):
                word = str[pos:i]
                if word not in dict.values():
                    dict[letter] = word
                    if helper(dict, p+1, i): return True
                    dict.pop(letter)
                else:
                    continue
            return False

        return helper({}, 0, 0)

There's a faster solution organized better and return earlier since the rest string cannot be shorter than rest pattern. Since there's many test cases in LeetCode OJ have very long patterns, this kind of optimization will do a lot of help.