290 Word Pattern

Given apatternand a stringstr, find ifstrfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter inpatternand a non-empty word instr.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.

2. pattern = "abba", str = "dog cat cat fish" should return false.

3. pattern = "aaaa", str = "dog cat cat dog" should return false.

4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assumepatterncontains only lowercase letters, andstrcontains lowercase letters separated by a single space.

The Idea: Use a bidirectional map to check for a one to one mapping between each character in the pattern and each word in the sentence.

Complexity: O(n) time and O(2n) space:

def wordPattern(self, pattern, str):
    """
    :type pattern: str
    :type str: str
    :rtype: bool
    """
    if len(pattern) != len(str.split()):
        return False
    chars_word = {}
    word_char = {}
    for char, word in zip(pattern, str.split()):
        if (chars_word.__contains__(char) and chars_word[char] != word)\
                or word_char.__contains__(word) and word_char[word] != char:
            return False
        elif not chars_word.__contains__(char):
            chars_word[char] = word
            word_char[word] = char

    return True