# LeetCode Solution, Easy, 290. Word Pattern

# [290. Word Pattern](https://leetcode.com/problems/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**.

#### 題目翻譯

這題會提供兩個變數，第一個變數 `pattern` 會給你一個規則，第二個變數 `s` 則是給你一個字串(字串中的字詞都用`' '`來隔開)。題目就是要用 `pattern` 去判斷是否 `s` 是否有符合規範。

### 解法解析

這題可以用一個或兩個 Hash Map 來去解。  
- Time complexity : O(N)，_N_ 是指 `pattern` 的長度  
- Space complexity : O(M)，_M_ 是指 `pattern` 中唯一字數的數量  

我這邊的範例是採用了單一 Hash Map 的方式來去解，但其他相差不多。  
第一步先篩選掉最好判斷的長度問題。兩個變數的字詞數不同和唯一字詞數不同的都先去掉。  
第二步就是開始去判斷規範了，使用一個 dict 來記錄判斷過的規則。這邊看要遍歷 `pattern` 或是拆分後的 `s` 都可以。一旦發現已經儲存的規範，但是跟應該對應的值不同的話就判斷失敗。  
最後當整個都遍歷後，就代表 `s` 是符合 `pattern` 規範的，所以回傳 True

#### 程式範例

##### Python

```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

```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

```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

```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

```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
    }
}
```