leetcode——290.单词规律

290. 单词规律

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的“遵循”指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例:

输入: pattern = "abba", str = "dog cat cat dog"

输出: true

说明:

输入中的 pattern 和字符串 str 都只包含小写字母。

输入中的字符串 str 由单个空格分隔成多个单词。

思路

这道题目要求我们判断字符串 str 是否遵循规律 pattern。我们可以使用哈希表来存储 pattern 中的字符与 str 中的单词之间的映射关系。

首先，我们将 pattern 转换为列表的形式，str 转换为单词列表的形式。然后，我们遍历 pattern 和 str 中的每个元素，并逐个进行匹配。

我们使用两个哈希表分别来记录 pattern 到 str 的映射和 str 到 pattern 的映射。通过遍历同时更新这两个哈希表，将 pattern 中的字符与 str 中的对应单词一一映射起来。

具体实现如下：

def wordPattern(pattern: str, str: str) -> bool:

    s = str.split()
    if len(pattern) != len(s):
        return False
    
    pattern_to_word = {}
    word_to_pattern = {}
    
    for i in range(len(pattern)):
        if pattern[i] in pattern_to_word:
            if pattern_to_word[pattern[i]] != s[i]:
                return False
        else:
            pattern_to_word[pattern[i]] = s[i]
        
        if s[i] in word_to_pattern:
            if word_to_pattern[s[i]] != pattern[i]:
                return False
        else:
            word_to_pattern[s[i]] = pattern[i]
    return True

算法的时间复杂度是 O(N)，其中 N 是 pattern 和 str 的长度。

测试示例

下面我们来测试一下这个方法：

pattern = "abba"

str = "dog cat cat dog"
print(wordPattern(pattern, str))  # 输出：True
pattern = "abba"
str = "dog cat cat fish"
print(wordPattern(pattern, str))  # 输出：False
pattern = "aaaa"
str = "dog cat cat dog"
print(wordPattern(pattern, str))  # 输出：False
pattern = "abba"
str = "dog dog dog dog"
print(wordPattern(pattern, str))  # 输出：False

结果与预期相符。

总结

本题是一道字符串匹配的问题，我们使用了哈希表来建立字符与单词之间的映射关系。这种解题思路可以解决很多相关的问题。

通过本题，我们不仅学会了如何使用哈希表来解决问题，还理解了哈希表的灵活性和实用性。哈希表在解决字符串匹配、映射关系等问题时非常高效，可以大大节省算法的时间复杂度。