Word Pattern
Easy · Arrays & Hashing · Hash Table · String
Problem
You are given a string pattern of lowercase letters and a string s of words separated by single spaces. s follows pattern when there is a bijection between the letters of the pattern and the words of s:
- the number of words equals the number of letters,
- each letter always stands for the same word, and
- each word always stands for the same letter (no two letters share a word).
Return true if s follows pattern, and false otherwise.
Examples
Input: pattern = "xyyx", s = "red blue blue red" Output: true
x ↔ red and y ↔ blue is a bijection.
Input: pattern = "xy", s = "go go" Output: false
Two different letters cannot both stand for "go".
Input: pattern = "aaa", s = "sun sun" Output: false
The pattern has three letters but s has only two words.
Constraints
- 1 <= len(pattern) <= 300
- pattern contains only lowercase English letters
- 1 <= len(s) <= 3000
- s contains only lowercase English letters and spaces
- s has no leading or trailing spaces, and its words are separated by single spaces
Approaches
- Baseline: compare every pair of positions — time O(n² · w), space O(n + L)
Follow-up
What if s had no spaces, so you had to decide where each word ends? Then you have to guess each new letter’s word and backtrack; the two maps are what prune the guesses (see the use case “The same pattern, with the spaces removed”).
Related problems
Start free on Cariara · Coding problems · System design studio
