# 290. Word Pattern

### 題目敘述

Given a `pattern` and a string `s`, find if `s` follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in `pattern` and a non-empty word in `s`.

Example 1:

``````Input: pattern = "abba", s = "dog cat cat dog"
Output: true
``````

Example 2:

``````Input: pattern = "abba", s = "dog cat cat fish"
Output: false
``````

Example 3:

``````Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
``````

Constraints:

• `1 <= pattern.length <= 300`
• `pattern` contains only lower-case English letters.
• `1 <= s.length <= 3000`
• `s` contains only lowercase English letters and spaces `' '`.
• `s` does not contain any leading or trailing spaces.
• All the words in `s` are separated by a single space.

### 解法解析

• Time complexity : O(N)，N 是指 `pattern` 的長度
• Space complexity : O(M)，M 是指 `pattern` 中唯一字數的數量

#### 程式範例

##### Python
``````class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
map_index = {}
words = s.split()

if len(pattern) != len(words):
return False
if len(set(pattern)) != len(set(words)):
return False

for i in range(len(words)):
c = pattern[i]
w = words[i]

if c in map_index and map_index[c] != w:
return False

map_index[c] = w

return True
``````
##### JavaScript
``````/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function (pattern, s) {
const words = s.split(' ');
const map = new Map();

if (words.length !== pattern.length) return false;
if (new Set(words).size !== new Set(pattern).size) return false;

for (let i = 0; i < pattern.length; i++) {
if (map.has(pattern[i]) && map.get(pattern[i]) !== words[i])
return false;
map.set(pattern[i], words[i]);
}
return true;
};
``````
##### Go
``````func wordPattern(pattern string, s string) bool {
pp := strings.Split(pattern, "")
sp := strings.Split(s, " ")
if len(pp) != len(sp) {
return false
}
mp := map[string]string{}
ms := map[string]string{}
for i, c := range pp {
msp, okp := mp[c]
cs, oks := ms[sp[i]]
if okp != oks || oks && (c != cs || msp != sp[i]) {
return false
}
mp[c] = sp[i]
ms[sp[i]] = c
}
return true
}
``````
##### Swift
``````class Solution {
func wordPattern(_ pattern: String, _ s: String) -> Bool {

let chars = [Character](pattern)
let words  = s.components(separatedBy: " ")

if chars.count != words.count { return false }

var letterToWordHash = [String: String]()
var wordToLetterHash = [String: String]()
for (index, letter) in letters.enumerated() {
let word = words[index]
if let existingWordHash = letterToWordHash[letter], word != existingWordHash { return false }
if let existingLetterHash = wordToLetterHash[word], letter != existingLetterHash { return false }

letterToWordHash[letter] = word
wordToLetterHash[word] = letter
}

return true
}
}
``````
##### Kotlin
``````class Solution {
fun wordPattern(pattern: String, s: String): Boolean {
val parseString = s.split(" ")

if (pattern.length != parseString.size) return false

val patternMap = hashMapOf<Char, Int>()
val parseStringMap = hashMapOf<String, Int>()

for (index in 0..pattern.lastIndex) {
if (patternMap[pattern[index]] != parseStringMap[parseString[index]]) return false

patternMap[pattern[index]] = index
parseStringMap[parseString[index]] = index
}

return true
}
}
``````