Word Pattern

easy string hash map

Problem

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.

Inputpattern = "abba", s = "dog cat cat dog"

Outputtrue

a ↔ dog, b ↔ cat is consistent.

pattern

sentence

def word_pattern(pattern, s):
    words = s.split(" ")
    if len(words) != len(pattern):
        return False
    c_to_w, w_to_c = {}, {}
    for c, w in zip(pattern, words):
        if c in c_to_w and c_to_w[c] != w:
            return False
        if w in w_to_c and w_to_c[w] != c:
            return False
        c_to_w[c] = w
        w_to_c[w] = c
    return True

function wordPattern(pattern, s) {
  const words = s.split(" ");
  if (words.length !== pattern.length) return false;
  const cToW = new Map(), wToC = new Map();
  for (let i = 0; i < pattern.length; i++) {
    const c = pattern[i], w = words[i];
    if (cToW.has(c) && cToW.get(c) !== w) return false;
    if (wToC.has(w) && wToC.get(w) !== c) return false;
    cToW.set(c, w);
    wToC.set(w, c);
  }
  return true;
}

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (words.length != pattern.length()) return false;
        Map<Character, String> cToW = new HashMap<>();
        Map<String, Character> wToC = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String w = words[i];
            if (cToW.containsKey(c) && !cToW.get(c).equals(w)) return false;
            if (wToC.containsKey(w) && wToC.get(w) != c) return false;
            cToW.put(c, w);
            wToC.put(w, c);
        }
        return true;
    }
}

bool wordPattern(string pattern, string s) {
    vector<string> words;
    string w;
    stringstream ss(s);
    while (ss >> w) words.push_back(w);
    if (words.size() != pattern.size()) return false;
    unordered_map<char, string> cToW;
    unordered_map<string, char> wToC;
    for (size_t i = 0; i < pattern.size(); ++i) {
        char c = pattern[i];
        const string& ww = words[i];
        if (cToW.count(c) && cToW[c] != ww) return false;
        if (wToC.count(ww) && wToC[ww] != c) return false;
        cToW[c] = ww;
        wToC[ww] = c;
    }
    return true;
}

Explanation

We want a bijection between pattern letters and words: each letter must always stand for the same word, and each word must always come from the same letter. The clean way to enforce both directions is to keep two maps that must stay consistent.

First, split the sentence into words. If the number of words doesn't equal the pattern length, there's no way to pair them up, so we return False right away.

Then we walk the pattern and the words together with zip. We keep c_to_w (letter to word) and w_to_c (word to letter). For each pair (c, w): if c is already linked to a different word, or w is already linked to a different letter, the mapping is broken and we return False. Otherwise we record both links.

Checking both directions is what prevents two letters from grabbing the same word. Without w_to_c, a pattern like "ab" on "dog dog" would wrongly pass.

Example: pattern = "abba", s = "dog cat cat dog". We set a→dog, b→cat, then re-see b→cat and a→dog, all consistent, so the answer is true.

Time: O(n) Space: O(n)