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.

題目翻譯

這題會提供兩個變數，第一個變數 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

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