Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一个字符组成的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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理