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:

  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 assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

思路

通过将pattern和string放入哈希表中，分别比较可以得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        tmp = ''
        words = []
        m = {}
        # 可以利用str.split内置函数，
        # 实现和下面代码一样的分割字符串取单词功能。
        for i in str:
            if (i == ' ' and tmp != ''):
                words.append(tmp)
                tmp = ''
            else:
                tmp += i
        words.append(tmp)
        ###### #### #### #### #### ######
        length = len(pattern)
        lengthstr = len(words)
        if (length != lengthstr):
            return False
        else:
            ### #### #### #### ##### #####
            for i in range(length):
                if (m.has_key(words[i])):
                    if ( m[words[i]] != pattern[i] ):
                        return False
                else:
                    m[words[i]] = pattern[i]
                    
            m = {}
            
            for i in range(length):
                if (m.has_key(pattern[i])):
                    if ( m[pattern[i]] != words[i] ):
                        return False
                else:
                    m[pattern[i]] = words[i]
        # 判断Map是否相等，可以直接使用 == 符号，而不需要用上面复杂的推导
        return True