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 TrueIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.