Word Pattern

Easy#290two maps

You get a pattern of letters and a string of words split by spaces. Find out whether the string follows the pattern: each letter always stands for the same word, and two different letters never stand for the same word. Our example: the pattern "abab" and "tick tock tick tock" — yes, a is tick and b is tock.

290 Word PatternWalkthrough · 1×

Example: the pattern "abab", the string "tick tock tick tock". Under them are both maps: letter → word and word → letter.

pattern0a1b2a3bwordsticktockticktocktoWordp → w—toLetterw → p—
not reached yetcurrent paircheckedthe clashfits the pattern

Split the string at the spaces: 4 words

01/25
restart · back · play · step
Speed
1function wordPattern(pattern, s):
2 words = split s at spaces
3 if len(words) != len(pattern):
4 return false
5 toWord = empty map
6 toLetter = empty map
7 for i from 0 to len(pattern) - 1:
8 p = pattern[i]; w = words[i]
9 if p in toWord and toWord[p] != w:
10 return false
11 if w in toLetter and toLetter[w] != p:
12 return false
13 toWord[p] = w; toLetter[w] = p
14 return true
state
words
[tick, tock, tick, tock]
toWord
–
toLetter
–
i
–
p
–
w
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. It is the check from Isomorphic Strings, only a letter stands for a whole word: toWord keeps letter → word, toLetter keeps word → letter.
  2. A different number of letters and words can never match, so that is checked first, before any map.
  3. One clash in either map means false. With no clash to the end, every letter always meets the same word and back: true.

Complexity

Time O(n), n is the length of the string: splitting it and one pass over the words. Memory O(n): the words and the two maps.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.