LeetCode 290 · Hashing

Word Pattern, explained with a picture

Matching symbols to words, both ways.

Hashing
▶ Watch it step by step

The problem

Does a sentence follow a pattern, with a one-to-one match between pattern letters and words?

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

Picture it

Picture matching symbols to words on two lists of cards. Each symbol must always mean the same word, and two different symbols can’t share a word. Two dictionaries check both directions.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Two maps (letter → word, word → letter). O(n).

Python solution

def word_pattern(pattern, s):
    words = s.split()
    if len(pattern) != len(words):
        return False
    p2w, w2p = {}, {}
    for p, w in zip(pattern, words):
        if p2w.get(p, w) != w or w2p.get(w, p) != p:
            return False
        p2w[p], w2p[w] = w, p
    return True

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.