Back to solutions

Word Pattern

EasyArrays

Check if a word sequence follows a single-letter pattern.

Open problem
Constraints
  • 1 <= |pattern| <= 300
  • Words are lowercase, space separated

Two-way mapping

Time O(n)Space O(n)

Split the words and check the counts match the pattern length. Then map each letter to a word and each word to a letter, failing if either map already disagrees. Both directions ensure a true one-to-one correspondence.

Key terms
bijection:
A pairing where each letter has a unique word and each word a unique letter.
tokenize:
Split the sentence into individual words on spaces.
bool wordPattern(const string& pattern, const string& words) {
    vector<string> ws; stringstream ss(words); string w;
    while (ss >> w) ws.push_back(w);
    if (pattern.size() != ws.size()) return false;
    unordered_map<char, string> c2w; unordered_map<string, char> w2c;
    for (size_t i = 0; i < pattern.size(); i++) {
        char c = pattern[i]; const string& word = ws[i];
        if (c2w.count(c) && c2w[c] != word) return false;
        if (w2c.count(word) && w2c[word] != c) return false;
        c2w[c] = word; w2c[word] = c;
    }
    return true;
}
Step by step
  1. Split the words string into a list; if its length differs from the pattern length, return false.
  2. For each position, take letter c and word w.
  3. If c already maps to a different word, or w already maps to a different letter, return false.
  4. Record c->w and w->c, then continue; return true if all positions agree.