题目

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

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

示例 1：

输入： pattern = "abba", s = "dog cat cat dog"

输出： true

示例 2：

输入： pattern = "abba", s = "dog cat cat fish"

输出： false

示例 3：

输入： pattern = "aaaa", s = "dog cat cat dog"

输出： false

方法一：哈希表

思路及解法

在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。

想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。

在实际代码中，我们枚举 $\textit{pattern}$ 中的每一个字符，利用双指针来均摊线性地找到该字符在 $\textit{str}$ 中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。

代码

class Solution {
    func wordPattern(_ pattern: String, _ s: String) -> Bool {
        let words: [String] = s.components(separatedBy: " ")
        if words.count != pattern.count {
            return false
        }
        
        let patterns = Array(pattern)
        var word2ch: [String : Character] = [:]
        var ch2word: [Character : String] = [:]
        for i in 0..<patterns.count {
            let ch: Character = patterns[i]
            let word: String = words[i]
            if nil != word2ch[word] && word2ch[word] != ch || nil != ch2word[ch] && ch2word[ch] != word {
                return false
            }
            word2ch[word] = ch
            ch2word[ch] = word
        }
        return true
    }
}

以上代码也可以优化后用一个字典解决：

class Solution {
    func wordPattern(_ pattern: String, _ s: String) -> Bool {
        let words: [String] = s.components(separatedBy: " ")
        if words.count != pattern.count {
            return false
        }
        
        let patterns = Array(pattern)
        var ch2word: [Character : String] = [:]
        for i in 0..<patterns.count {
            let ch: Character = patterns[i]
            let word: String = words[i]
            if nil == ch2word[ch] {
                if !ch2word.values.contains(word) {
                    ch2word[ch] = word
                } else {
                    return false
                }
            } else if ch2word[ch] != word {
                return false
            }
        }
        return true
    }
}

复杂度分析

时间复杂度： $O(n+m)$ ，其中 $n$ 为 $\textit{pattern}$ 的长度， $m 为 \textit{str}$ 的长度。插入和查询哈希表的均摊时间复杂度均为 $O(n + m)$ 。每一个字符至多只被遍历一次。
空间复杂度： $O(n+m)$ ，其中 $n$ 为 $\textit{pattern}$ 的长度， $m$ 为 $\textit{str}$ 的长度。最坏情况下，我们需要存储 $\textit{pattern}$ 中的每一个字符和 $\textit{str}$ 中的每一个字符串。