题目
给定一种规律 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
方法一：哈希表
思路及解法
在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。
想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。
在实际代码中，我们枚举 中的每一个字符，利用双指针来均摊线性地找到该字符在
中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。
代码
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
}
}
复杂度分析
时间复杂度：
，其中
为
的长度，
的长度。插入和查询哈希表的均摊时间复杂度均为
。每一个字符至多只被遍历一次。
空间复杂度：
为
的长度。最坏情况下，我们需要存储
