290.word-pattern.md

290. Word Pattern

Test Cases

Normal Cases

Input: "abba", "dog cat cat dog"
Output: true

Input: "abba", "dog cat cat fish"
Output: false

Edge / Corner Cases

• The same pattern but mapped to different splits.

Input: "aa", "dog cat"
Output: false

• The same word but mapped to different patterns.

Input: "ab", "dog dog"
Output: false

Hash Table

We can use a hash table to map the character to the word. We can use an array to store the mapping. We can also use a hash set to check if the word is already mapped to a character.

Please pay attention to the edge cases where the same pattern is mapped to different splits or the same word is mapped to different patterns. If we just only track pattern -> word mapping, we might allow different pattern to map to the same word. We can use a reversed map or set to check if the word is already mapped to a character or added.

fun wordPattern(pattern: String, s: String): Boolean {
    val split = s.split("\\s+".toRegex())
    if (pattern.length != split.size) return false

    val match = Array<String>(26) { "" }

    // Or we can use reversed map to check if the word is already mapped to a character.
    val seen = hashSetOf<String>()
    for (i in 0 until pattern.length) {
        val c = pattern[i]
        if (match[c - 'a'].isEmpty()) {
            // Same splits but mapped to different patterns.
            // "ab", "dog dog"
            if (seen.contains(split[i])) return false
            match[c - 'a'] = split[i]
            seen.add(split[i])
        } else {
            if (match[c - 'a'] != split[i]) return false
        }
    }
    return true
}

// Or equivalently, we use two map to store the mapping: pattern to word and word to pattern.
fun wordPattern(pattern: String, s: String): Boolean {
    val splits = s.split("\\s+".toRegex())
    if (pattern.length != splits.size)
        return false

    val wordToChar = HashMap<String, Char>()
    val charToWord = HashMap<Char, String>()

    for (i in pattern.indices) {
        val char = pattern[i]
        val word = splits[i]

        val mappedWord = charToWord[char]
        val mappedChar = wordToChar[word]

        if (mappedWord == null && mappedChar == null) {
            wordToChar[word] = char
            charToWord[char] = word
        } else if (char != mappedChar || word != mappedWord) {
            return false
        }
    }
    return true
}

• Time Complexity: O(P + S) where P and S is the length of pattern and split.
• Space Complexity: O(P + S).