290. Word Pattern Easy

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. Specifically:

• Each letter in pattern maps to exactly one unique word in s.
• Each unique word in s maps to exactly one letter in pattern.
• No two letters map to the same word, and no two words map to the same letter.

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

Approach

Input: A string pattern and a string s

Output: Determine if s follows the same pattern

This is a Hash Table problem.

Use two hash tables keyMap and valMap to record key -> val and val -> key.

Split s into an array arr.

Let pattern[i] be the key and arr[i] be the val.

Iterate through the string pattern (and concurrently arr):

• Check if the word corresponding to key in keyMap is consistent with arr[i].
• Check if the character corresponding to val in valMap is consistent with pattern[i].

Then record them in the corresponding hash tables.

If all checks are correct, return true.

Implementation

python

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # Split string s into a word array by space
        arr = s.split(' ')

        # If the length of pattern and the number of words are different, it definitely does not follow the pattern
        if len(pattern) != len(arr):
            return False

        # Establish bidirectional mapping:
        # keyMap: pattern character -> word
        # valMap: word -> pattern character
        keyMap = {}
        valMap = {}

        # Iterate through pattern and arr
        for i in range(len(pattern)):
            key = pattern[i]  # Current pattern character
            val = arr[i]      # Current word

            # If the pattern character has appeared, but the corresponding word is inconsistent ⇒ conflict
            if key in keyMap and keyMap[key] != val:
                return False

            # If the word has appeared, but the corresponding pattern character is inconsistent ⇒ conflict
            if val in valMap and valMap[val] != key:
                return False

            # Establish/Confirm bidirectional mapping
            keyMap[key] = val
            valMap[val] = key

        # If traversal finishes without conflict, it implies it follows the pattern
        return True

javascript

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function(pattern, s) {
    const arr = s.split(' ');

    if (pattern.length !== arr.length) return false;

    const keyMap = new Map;
    const valMap = new Map;

    for (let i = 0; i < pattern.length; i++) {
        const key = pattern[i];
        const val = arr[i];

        if (keyMap.has(key) && keyMap.get(key) !== val) return false;
        if (valMap.has(val) && valMap.get(val) !== key) return false;

        keyMap.set(key, val);
        valMap.set(val, key);
    }

    return true;
};

Complexity Analysis

• Time Complexity: O(n + m) where n is length of pattern and m is length of string s
• Space Complexity: O(n + m) for storing words and hash maps

Links

290. Word Pattern (English)290. 单词规律 (Chinese)