Practice › Hashing & Two Pointers
Word Pattern
Easy · Hashing & Two Pointers · Asked at Amazon, Uber, Dropbox, Zoho
Does the sentence follow the pattern? Each letter of pattern must map to exactly one word, and each word to exactly one letter (a one-to-one match), in order. Print YES or NO.
Input
First line: pattern (lowercase letters). Second line: words separated by single spaces.
Output
YES or NO.
Constraints
- 1 ≤ |pattern| ≤ 300
- Words are lowercase, up to 3000 characters in total
Use two maps (letter → word and word → letter). Different lengths mean NO immediately.
Example 1
Input
abba dog cat cat dog
Output
YES
Example 2
Input
abba dog dog dog dog
Output
NO
Hints
- If the number of words differs from the pattern length, the answer is NO.
- One map is not enough: "abba" vs "dog dog dog dog" passes a letter→word check. Also check word→letter.
Approach
Split the second line into words. Walk both sequences together, maintaining letter → word and word → letter maps. If either map already has an entry that disagrees with the current pair, it is not a bijection — print NO. Otherwise record the pair. Surviving the whole walk means YES.
Complexity: O(total length) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string pat, line, w;
getline(cin, pat);
getline(cin, line);
stringstream ss(line);
vector<string> words;
while (ss >> w) words.push_back(w);
while (!pat.empty() && isspace((unsigned char)pat.back())) pat.pop_back();
if (words.size() != pat.size()) {
cout << "NO\n";
return 0;
}
map<char, string> a;
map<string, char> b;
for (size_t i = 0; i < pat.size(); i++) {
if ((a.count(pat[i]) && a[pat[i]] != words[i]) || (b.count(words[i]) && b[words[i]] != pat[i])) {
cout << "NO\n";
return 0;
}
a[pat[i]] = words[i];
b[words[i]] = pat[i];
}
cout << "YES\n";
return 0;
}Python solution
import sys
lines = sys.stdin.read().split("\n")
pat, words = lines[0].strip(), lines[1].split()
ok = len(pat) == len(words)
a, b = {}, {}
for c, w in zip(pat, words):
if a.get(c, w) != w or b.get(w, c) != c:
ok = False
break
a[c], b[w] = w, c
print("YES" if ok else "NO")Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String pat = br.readLine().trim();
String[] words = br.readLine().trim().split("\\s+");
if (words.length != pat.length()) {
System.out.println("NO");
return;
}
Map<Character, String> a = new HashMap<>();
Map<String, Character> b = new HashMap<>();
for (int i = 0; i < words.length; i++) {
char c = pat.charAt(i);
if ((a.containsKey(c) && !a.get(c).equals(words[i])) || (b.containsKey(words[i]) && b.get(words[i]) != c)) {
System.out.println("NO");
return;
}
a.put(c, words[i]);
b.put(words[i], c);
}
System.out.println("YES");
}
}