Word Pattern II

Question Description

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 substring in str.

Examples:

pattern = "abab", str = "redblueredblue" should return true.

pattern = "aaaa", str = "asdasdasdasd" should return true.

pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes: You may assume both pattern and str contains only lowercase letters.

Solution

Use two dictionary to record the corresponding relationship between pattern and str.

Every time, if the corresponding for a pattern exists, we check before we go to next recursive call; if not, we try: if succeed, return True and end the DFS search; if not, return False and delete the trial key in the dictionaries.

class Solution(object):
    def wordPatternMatch(self, pattern, astr):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        ptndict, strdict = {}, {}
        for c in pattern:
            ptndict[c] = ''
        return self.dfs(pattern, astr, ptndict, strdict, 0, 0)

    def dfs(self, pattern, astr, ptndict, strdict, s1, s2):
        if s1 == len(pattern) or s2 == len(astr):
            if s1 != len(pattern) or s2 != len(astr):
                return False
            else:
                return True
        if ptndict[pattern[s1]] != '':
            l = len(ptndict[pattern[s1]])
            if s2 + l > len(astr) or astr[s2:s2 + l] != ptndict[pattern[s1]]:
                return False
            return self.dfs(pattern, astr, ptndict, strdict, s1 + 1, s2 + l)
        else:
            for i in range(s2, len(astr)):
                if astr[s2:i + 1] not in strdict:
                    ptndict[pattern[s1]] = astr[s2:i + 1]
                    strdict[astr[s2:i + 1]] = pattern[s1]
                    if self.dfs(pattern, astr, ptndict, strdict, s1 + 1, i + 1):
                        return True
                    ptndict[pattern[s1]] = ''
                    del strdict[astr[s2:i + 1]]
            return False