leetcode每日一题：290. 单词规律
题目链接：https://leetcode-cn.com/problems/word-pattern
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true示例 2:
输入:pattern = "abba", str = "dog cat cat fish"
输出: false示例 3:
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false示例 4:
输入: pattern = "abba", str = "dog dog dog dog"
输出: false说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
思路：
首先通过空格将字符串分开为对应的字符列表，然后判断每个小的字符串是否与pattern中字符一一对应，注意，这里是一对一的关系，即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。
想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。
在实际代码中，我们枚举 pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在str中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
if pattern is None:
if s is None:
return True
else:
return False
res = {}
length1 = len(pattern)
s_l = s.split(' ')
length2 = len(s_l)
if length1 != length2:
return False
'''
# 双双对应
for i in range(length1):
a = pattern[i]
b = s_l[i]
if a not in res:
res[a] = b
if a in res:
c = res[a]
if b != c:
return False
res2 = {}
for j in range(length2):
a = pattern[j]
b = s_l[j]
if b not in res2:
res2[b] = a
else:
c = res2[b]
if c != a:
return False
return True
'''
# 使用zip
res1 = dict()
res2 = dict()
for ch, word in zip(pattern, s_l):
if (word in res1 and res1[word] != ch) or (ch in res2 and res2[ch] != word):
return False
res1[word] = ch
res2[ch] = word
return True本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读