Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Word Pattern

Try it yourself
EasyProblemExternal link

Description

You get a pattern and a string s of words.

Decide whether s follows pattern: there must be a one-to-one match between the letters of pattern and the words of s. Each letter always stands for the same word, and no two letters stand for the same word.

Examples

Example 1

Input: pattern = "abba", s = "dog cat cat dog"

Output: true

Explanation: a is dog and b is cat, both ways round: true.

Example 2

Input: pattern = "abba", s = "dog cat cat fish"

Output: false

Explanation: a would have to be both dog and fish: false.

Example 3

Input: pattern = "aaaa", s = "dog cat cat dog"

Output: false

Explanation: a would have to be dog and cat at once: false.

Constraints

  • 1 ≤ pattern.length ≤ 300
  • pattern contains only lowercase English letters.
  • 1 ≤ s.length ≤ 3000
  • s contains only lowercase English letters and spaces.
  • s has no leading or trailing spaces, and its words are separated by single spaces.

Editorial

Brute Force

Intuition

A one-to-one match means this, for every two positions i and j: the letters there are equal exactly when the words there are equal. So check that for every pair of positions (after checking that there are as many words as letters).

Step-by-Step Explanation

Let's check pattern = "abba", s = "dog cat cat fish":

  1. Positions 0 and 1 hold the letters a and b and the words dog and cat. Both pairs are different, which agrees.
  2. Positions 0 and 2 hold the letters a and b and the words dog and cat. Both pairs are different, which agrees.
  3. Positions 0 and 3 hold the letters a and a and the words dog and fish. The letters are the same but the words are different, so the answer is false.

Compare Every Pair of Positions — The row is the words. Each step compares two positions' letters and words.

Algorithm

  1. Split s into words; if there are not as many as letters, return false.
  2. For every pair i < j: if pattern[i] == pattern[j] differs from words[i] == words[j], return false.
  3. Return true.

Code

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> w;
        stringstream in(s);
        for (string x; in >> x;) w.push_back(x);
        int n = pattern.size();
        if ((int)w.size() != n) return false;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)     // same letter exactly when same word, for every pair
                if ((pattern[i] == pattern[j]) != (w[i] == w[j])) return false;
        return true;
    }
};

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        w = s.split()
        n = len(pattern)
        if len(w) != n:
            return False
        for i in range(n):
            for j in range(i + 1, n):           # same letter exactly when same word, for every pair
                if (pattern[i] == pattern[j]) != (w[i] == w[j]):
                    return False
        return True

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] w = s.split(" ");
        int n = pattern.length();
        if (w.length != n) return false;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)     // same letter exactly when same word, for every pair
                if ((pattern.charAt(i) == pattern.charAt(j)) != w[i].equals(w[j])) return false;
        return true;
    }
}

var wordPattern = function(pattern, s) {
    const w = s.split(' ');
    const n = pattern.length;
    if (w.length !== n) return false;
    for (let i = 0; i < n; i++)
        for (let j = i + 1; j < n; j++)         // same letter exactly when same word, for every pair
            if ((pattern[i] === pattern[j]) !== (w[i] === w[j])) return false;
    return true;
};

Complexity Analysis

Time Complexity: O(n² · k)

n(n − 1)/2 pairs of n positions, each comparing words of up to k letters.

Space Complexity: O(n · k) for the words

Why This Approach Is Not Efficient

With 300 positions it's about 45,000 pairs, which passes here, but it grows with the square of n. Instead of comparing every pair, remember what each letter and each word has been matched with so far: then each position is checked once.

Optimal Approach - Two Maps

Intuition

Walk the letters and words together, keeping two maps: letter to word, and word to letter. At each position, the letter must not already stand for a different word, and the word must not already belong to a different letter. If both hold, record the pair.

Why two maps? One map from letters to words only checks that each letter keeps its word. It can't see two letters taking the same word: with "abba" and "dog dog dog dog", a → dog and b → dog both pass. The second map catches that. And check the lengths first: zipping a 4-letter pattern with 3 words just stops early.

Step-by-Step Explanation

Let's check pattern = "abba", s = "dog cat cat fish" again:

  1. Keep two maps, letter to word (shown) and word to letter. Each position must agree with both.
  2. a and dog agree with both maps, so record a as dog.
  3. b and cat agree with both maps, so record b as cat.
  4. b and cat agree with both maps, so record b as cat.
  5. a already stands for dog, not fish, so the answer is false.

Match Letters and Words Both Ways — The row is the words; the table is the letter-to-word map. Each step checks one position against both maps.

Algorithm

  1. Split s into words; if there are not as many as letters, return false.
  2. For each position: if the letter maps to a different word, or the word maps to a different letter, return false. Otherwise record the pair in both maps.
  3. Return true.

Code

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        stringstream in(s);
        for (string w; in >> w;) words.push_back(w);
        if (words.size() != pattern.size()) return false;
        unordered_map<char, string> letterToWord;    // both directions, so the match is one-to-one
        unordered_map<string, char> wordToLetter;
        for (size_t i = 0; i < words.size(); i++) {
            char c = pattern[i];
            const string& w = words[i];
            if ((letterToWord.count(c) && letterToWord[c] != w) || (wordToLetter.count(w) && wordToLetter[w] != c))
                return false;                       // c already has another word, or w another letter
            letterToWord[c] = w;
            wordToLetter[w] = c;
        }
        return true;
    }
};

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(words) != len(pattern):
            return False
        letter_to_word, word_to_letter = {}, {}     # both directions, so the match is one-to-one
        for c, w in zip(pattern, words):
            if letter_to_word.get(c, w) != w or word_to_letter.get(w, c) != c:
                return False                        # c already has another word, or w another letter
            letter_to_word[c], word_to_letter[w] = 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> letterToWord = new HashMap<>();   // both directions, so the match is one-to-one
        Map<String, Character> wordToLetter = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            char c = pattern.charAt(i);
            String w = words[i];
            if (!letterToWord.getOrDefault(c, w).equals(w) || wordToLetter.getOrDefault(w, c) != c)
                return false;                       // c already has another word, or w another letter
            letterToWord.put(c, w);
            wordToLetter.put(w, c);
        }
        return true;
    }
}

var wordPattern = function(pattern, s) {
    const words = s.split(' ');
    if (words.length !== pattern.length) return false;
    const letterToWord = new Map(), wordToLetter = new Map();   // both directions, so the match is one-to-one
    for (let i = 0; i < words.length; i++) {
        const c = pattern[i], w = words[i];
        if ((letterToWord.has(c) && letterToWord.get(c) !== w) || (wordToLetter.has(w) && wordToLetter.get(w) !== c))
            return false;                           // c already has another word, or w another letter
        letterToWord.set(c, w);
        wordToLetter.set(w, c);
    }
    return true;
};

Complexity Analysis

Time Complexity: O(n · k)

One pass over the positions; each step hashes one word of up to k letters.

Space Complexity: O(n · k) for the words and the maps

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Checking letter to word only. if letter_to_word.get(c, w) != w:

On pattern = "abba", s = "dog dog dog dog", it returns true; the answer is false. One map from letters to words checks that each letter keeps its word, but not that two letters don't share one: a and b can both become dog. Keep the reverse map too.

Checking word to letter only. if word_to_letter.get(w, c) != c:

On pattern = "abcca", s = "dog cat fish fish cow", it returns true; the answer is false. The reverse map alone has the mirror hole: one letter can stand for two different words. Check both directions.

Skipping the length check. for c, w in zip(pattern, words): # with no length check first

On pattern = "aaaa", s = "dog dog dog", it returns true; the answer is false. zip stops at the shorter of the two, so extra letters or extra words are never looked at. Compare the lengths first.

Comparing how many distinct letters and words. return len(set(words)) == len(set(pattern))

On pattern = "abba", s = "dog cat dog cat", it returns true; the answer is false. Two letters and two words can still be in different shapes: "abba" against "dog cat dog cat". The match has to hold position by position.

Where This Pattern Is Taught

This problem practises one-to-one matching with two hash maps. It's taught in Grouping and Matching with Hash Maps.