leetcode | 290.单词规律

290.单词规律

题目描述

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:
输入: pattern = “abba”, str = “dog cat cat dog”
输出: true

题目链接

思路

1.哈希表
在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。
想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。
在实际代码中，我们枚举 pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在 str 中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。

代码

class Solution(object):
    def wordPattern(self, pattern, s):
        """
        :type pattern: str
        :type s: str
        :rtype: bool
        """
        word2ch = dict()
        ch2word = dict()
        words = s.split()
        if len(pattern) != len(words):
            return False

        for ch, word in zip(pattern, words):
            if (word in word2ch and word2ch[word] != ch) or (ch in ch2word and ch2word[ch] != word):
                return False
            word2ch[word] = ch
            ch2word[ch] = word

        return True

    def wordPattern(self, pattern, s):
        dct = dict()
        s = s.split(' ')
        if len(s) != len(pattern):  # 两个字符串长度不相同，返回False
            return False

        for i in range(len(pattern)):
            if pattern[i] not in dct:  # 如果pattern[i]不在字典中，此时要加入pattern[i]
                if s[i] not in dct.values():  # 如果s[i]还未存在，则加入新的映射
                    dct[pattern[i]] = s[i]
                else:
                    return False  # 但是如果与dct[pattern[i]]对应的s[i]已经存在字典的值中，说明不是唯一映射
            else:
                if dct[pattern[i]] != s[i]:  # 如果pattern[i]在字典中，但是dct[pattern[i]]的值不等于s[i]，说明已存在其他映射
                    return False
        return True



if __name__ == '__main__':
    slt = Solution()
    res = slt.wordPattern1("abba", "dog cat cat dog")
    print(res)