给定一个字符组成的pattern,和一个单词组成的字符串(单词以空格分开),问字符串是否满足单词的pattern,例:
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
写法一:用字典记录从每个单词到一个字母的映射,再用一个set保存已经拥有映射值的字母(否则example3会错)
1 #290
2 #Runtime: 18 ms (Beats 81.66%)
3 #Memory: 13.2 MB (Beats 98.30%)
4
5 class Solution(object):
6 def wordPattern(self, pattern, s):
7 """
8 :type pattern: str
9 :type s: str
10 :rtype: bool
11 """
12 str_lst = s.split()
13 str_dct = {}
14 chr_set = set()
15 i = 0
16 if len(pattern) != len(str_lst):
17 return False
18 for i in range(len(str_lst)):
19 if str_lst[i] in str_dct:
20 if str_dct[str_lst[i]] != pattern[i]:
21 return False
22 else:
23 if pattern[i] in chr_set:
24 return False
25 chr_set.add(pattern[i])
26 str_dct[str_lst[i]] = pattern[i]
27 i += 1
28 return True
写法二:用字典记录从每个单词到一个字母的映射,每次查找字典的values来判断是否与已有的映射值重复(这样时间效率不如set)
1 #290
2 #Runtime: 36 ms (Beats 15.62%)
3 #Memory: 13.5 MB (Beats 71.99%)
4
5 class Solution(object):
6 def wordPattern(self, pattern, s):
7 """
8 :type pattern: str
9 :type s: str
10 :rtype: bool
11 """
12 str_list = s.split(" ")
13 dt = {}
14 if len(pattern) != len(str_list):
15 return False
16 for i in range(0, len(pattern)):
17 if dt.has_key(pattern[i]):
18 if dt[pattern[i]] != str_list[i]:
19 return False
20 else:
21 if str_list[i] in dt.values():
22 return False
23 dt[pattern[i]] = str_list[i]
24 return True