291. Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

• pattern = "abba", str = "redblueredblue" should return true.
• pattern = "aaaa", str = "asdasdasdasd" should return true.
• pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:

You may assume pattern and str contain only lowercase letters.

Solution: HashMap & DFS

class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        char_word = dict()
        word_char = dict()
        pat_len = len(pattern)
        str_len = len(str)

        def dfs(i, j):
            if i == pat_len and j == str_len:
                return True
            if i >= pat_len or j >= str_len or pat_len - i > str_len - j:
                return False

            char = pattern[i]
            if char in char_word:
                word = char_word[char]
                k = j + len(word)
                if str.find(word, j, k) != -1:
                    return dfs(i + 1, k)
                return False

            for k in xrange(j, len(str)):
                word = str[j: k + 1]
                if word in word_char:
                    continue
                char_word[char] = word
                word_char[word] = char
                if dfs(i + 1, k + 1):
                    return True
                del char_word[char]
                del word_char[word]
            return False

        return dfs(0, 0)

Lessons:

• When pattern length is larger than string length, simply return false.

Related:

• 290. Word Pattern