卖萌的弱渣

I am stupid, I am hungry.

Word Pattern

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.

Solution

Corner Cases: * “abba” -> “dog dog dog dog” * “abba” -> “dog cat cat fish”

(Word-Pattern.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        if not pattern:
            return False
        hash_table = dict()
        s_list = str.split(" ")
        if len(pattern) != len(s_list):
            return False
        for i in range(len(pattern)):
            if pattern[i] not in hash_table:
                # "abba" -> "dog dog dog dog"
                if s_list[i] in hash_table.values():
                    return False
                hash_table[pattern[i]] = s_list[i]
            else:
                if hash_table[pattern[i]] != s_list[i]:
                    return False
        return True