Word Pattern

Question

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 = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Tags

• String
• Hashmap

Thought

Use the hashmap to represent the mapping relation between the pattern string and the str string. The process is almost the same to the Isomorph Strings.

Code

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        patternList = list(pattern)
        strList = str.split(' ')
        if len(patternList) != len(strList):
            return False
        sourceMap, targetMap = dict(), dict()
        for i in xrange(len(patternList)):
            source = sourceMap.get(strList[i], None)
            target = targetMap.get(patternList[i], None)
            if source is None and target is None:
                sourceMap[strList[i]] = patternList[i]
                targetMap[patternList[i]] = strList[i]
            elif source != patternList[i] or target != strList[i]:
                return False
        return True