題目
給定一種規(guī)律 pattern 和一個字符串 s擂啥，判斷 s 是否遵循相同的規(guī)律哄陶。
這里的 遵循 指完全匹配，例如哺壶， pattern 里的每個字母和字符串 s 中的每個非空單詞之間存在著雙向連接的對應(yīng)規(guī)律闹击。
示例 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
方法一：哈希表
思路及解法
在本題中，我們需要判斷字符與字符串之間是否恰好一一對應(yīng)主之。即任意一個字符都對應(yīng)著唯一的字符串纠俭，任意一個字符串也只被唯一的一個字符對應(yīng)。在集合論中粗截，這種關(guān)系被稱為「雙射」。
想要解決本題，我們可以利用哈希表記錄每一個字符對應(yīng)的字符串旬盯，以及每一個字符串對應(yīng)的字符。然后我們枚舉每一對字符與字符串的配對過程翎猛，不斷更新哈希表胖翰，如果發(fā)生了沖突，則說明給定的輸入不滿足雙射關(guān)系切厘。
在實(shí)際代碼中萨咳，我們枚舉 中的每一個字符，利用雙指針來均攤線性地找到該字符在
中對應(yīng)的字符串疫稿。每次確定一個字符與字符串的組合培他，我們就檢查是否出現(xiàn)沖突，最后我們再檢查兩字符串是否比較完畢即可遗座。
代碼
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
}
}
以上代碼也可以優(yōu)化后用一個字典解決：
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
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
舀凛，其中
為
的長度，
的長度途蒋。插入和查詢哈希表的均攤時(shí)間復(fù)雜度均為
猛遍。每一個字符至多只被遍歷一次。
空間復(fù)雜度：
為
的長度。最壞情況下宽堆，我們需要存儲
