Word Pattern Matcher — Problem Statement & Solution Guide
Problem Description
You are provided with a pattern string p consisting of lowercase English letters and a sentence s composed of words separated by single spaces. The goal is to determine if s adheres to the structural mapping defined by p. A valid mapping requires a strict bijection: every distinct character in p must correspond to a unique word in s, and conversely, every word in s must be mapped from exactly one character in p. This implies that if two characters in p are identical, their corresponding words in s must be identical, and if two characters in p are different, their corresponding words in s must be different. Return true if such a one-to-one correspondence exists between the characters of p and the words of s; otherwise, return false.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Word Pattern Matcher"
WHY DOES IT MATTER?
Bijection enforcement guarantees that the pattern uniquely defines the sentence structure, preventing ambiguous or overlapping mappings that could lead to incorrect interpretations in applications like template rendering or data serialization.
OPTIMIZATION CHALLENGE
The challenge is to detect mapping conflicts in constant time per element, which is achieved by maintaining two hash maps that enforce forward and reverse constraints simultaneously, eliminating the need for expensive set lookups or backtracking.
REAL-WORLD CONNECTION
In microservice architectures, routing rules often map a URL pattern to a specific service endpoint. Ensuring a one-to-one mapping between pattern segments and services prevents routing conflicts and guarantees deterministic request handling.
Always initialize both maps at the start and perform the conflict checks in a single pass; this keeps the code clean and avoids subtle bugs where one direction of the mapping is updated but not the other.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The Word Pattern Matcher problem is a classic example of a bijective mapping problem, where each character in a pattern string must map to a unique word in a sentence and vice versa. A naive approach would generate all possible word-to-character assignments and test each, leading to exponential time complexity and quickly becoming infeasible for moderate input sizes. The optimal solution leverages two hash maps (or dictionaries) to maintain forward and reverse mappings simultaneously. By iterating through the pattern and the split words in lockstep, we can check and establish mappings in constant time per element, guaranteeing an overall linear time complexity of O(n) where n is the number of words. This approach also ensures that any conflict—such as a character mapping to two different words or a word mapping to two different characters—is detected immediately, allowing for an early exit.
The key insight is that the bijection property can be enforced by maintaining two separate maps: one from pattern characters to words, and another from words to pattern characters. This dual mapping ensures that both directions of the relationship are validated without the need for expensive set operations or backtracking. Because each word and character is processed only once, the algorithm scales gracefully even for long sentences and complex patterns, making it suitable for real-world applications such as template matching, URL routing, or configuration validation.
In distributed systems, similar bijective constraints arise when assigning unique identifiers to resources or ensuring that a user ID maps to a single session token. The same hash-based strategy guarantees consistency and fast lookups across nodes, illustrating why this pattern is a foundational tool in both algorithm design and system architecture.
Interview Questions on This Problem
Q1How would you modify the algorithm if the pattern string could contain uppercase letters and the sentence words could be case-insensitive?
Treat the pattern characters and words in a case-insensitive manner by normalizing them (e.g., converting to lowercase) before performing the mapping. The rest of the algorithm remains unchanged, but you must ensure that the normalization step is applied consistently to both the pattern and the words to avoid false mismatches.
Q2In a production system, you need to validate a large batch of pattern-sentence pairs concurrently. What concurrency considerations would you apply to the mapping algorithm?
Because the algorithm is inherently stateless per pair, you can process each pair in parallel using thread pools or async workers. Ensure that the hash maps are local to each thread to avoid contention, and if you aggregate results, use thread-safe collections or atomic counters to collect outcomes without race conditions.
Q3Suppose the sentence can contain punctuation attached to words (e.g., "hello," "world!"). How would you adapt the solution to handle such cases?
Preprocess the sentence by stripping or normalizing punctuation from each word before splitting or after splitting. Alternatively, use a regex to split on word boundaries, ensuring that punctuation does not become part of the word token. The mapping logic then operates on clean tokens, preserving the bijection property.
Examples
Input
p = "abba", s = "dog cat cat dog"
Output
true
Explanation: Split `s` into words: ["dog", "cat", "cat", "dog"]. Map 'a' -> "dog", 'b' -> "cat". Check reverse: "dog" -> 'a', "cat" -> 'b'. All mappings are consistent and bijective. Return true.
Input
p = "abba", s = "dog cat cat fish"
Output
false
Explanation: Split `s` into words: ["dog", "cat", "cat", "fish"]. Map 'a' -> "dog", 'b' -> "cat". At index 3, 'a' maps to "fish", but 'a' was previously mapped to "dog". Conflict detected. Return false.
Input
p = "abc", s = "dog cat dog"
Output
false
Explanation: Split `s` into words: ["dog", "cat", "dog"]. Map 'a' -> "dog", 'b' -> "cat". At index 2, 'c' maps to "dog". However, "dog" is already mapped to 'a'. This violates the bijection constraint (one word cannot map to two different characters). Return false.
Input
p = "xyz", s = "apple banana cherry"
Output
true
Explanation: Split `s` into words: ["apple", "banana", "cherry"]. Map 'x' -> "apple", 'y' -> "banana", 'z' -> "cherry". All characters are distinct and all words are distinct. The mapping is bijective. Return true.
Constraints
- 1 <= p.length <= 300
- p consists of lowercase English letters.
- 1 <= s.length <= 3000
- s consists of lowercase English letters and spaces.
- All words in s are separated by a single space and have no leading or trailing spaces.
Optimal Approach & Strategy
Use two hash maps to maintain forward and reverse bijections while iterating once over the pattern and words, achieving linear time.
Brute Force Approach
Generate all possible assignments of words to pattern letters and test each mapping against the sentence, which leads to factorial time complexity.
Verified Code Solutions
function wordPattern(p, s) {
const words = s.split(' ');
if (p.length !== words.length) return false;
const c2w = new Map();
const w2c = new Map();
for (let i = 0; i < p.length; i++) {
const c = p[i];
const w = words[i];
if (c2w.has(c) && c2w.get(c) !== w) return false;
if (w2c.has(w) && w2c.get(w) !== c) return false;
c2w.set(c, w);
w2c.set(w, c);
}
return true;
}
// Example usage
const p = "abba";
const s = "dog cat cat dog";
console.log(wordPattern(p, s));#include <bits/stdc++.h>
using namespace std;
bool wordPattern(const string& p, const string& s) {
vector<string> words;
string word;
stringstream ss(s);
while (ss >> word) {
words.push_back(word);
}
if (p.size() != words.size()) return false;
unordered_map<char, string> c2w;
unordered_map<string, char> w2c;
for (size_t i = 0; i < p.size(); ++i) {
char c = p[i];
const string& w = words[i];
if (c2w.count(c) && c2w[c] != w) return false;
if (w2c.count(w) && w2c[w] != c) return false;
c2w[c] = w;
w2c[w] = c;
}
return true;
}
int main() {
string p = "abba";
string s = "dog cat cat dog";
cout << (wordPattern(p, s) ? "true" : "false") << endl;
return 0;
}
import java.util.*;
public class WordPatternMatcher {
public static boolean wordPattern(String p, String s) {
String[] words = s.split(" ");
if (p.length() != words.length) return false;
Map<Character, String> c2w = new HashMap<>();
Map<String, Character> w2c = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
char c = p.charAt(i);
String w = words[i];
if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
if (w2c.containsKey(w) && w2c.get(w) != c) return false;
c2w.put(c, w);
w2c.put(w, c);
}
return true;
}
public static void main(String[] args) {
String p = "abba";
String s = "dog cat cat dog";
System.out.println(wordPattern(p, s));
}
}
def wordPattern(p: str, s: str) -> bool:
words = s.split()
if len(p) != len(words):
return False
c2w = {}
w2c = {}
for c, w in zip(p, words):
if c in c2w and c2w[c] != w:
return False
if w in w2c and w2c[w] != c:
return False
c2w[c] = w
w2c[w] = c
return True
if __name__ == "__main__":
p = "abba"
s = "dog cat cat dog"
print(wordPattern(p, s))
function wordPattern(p, s) {
const words = s.split(' ');
if (p.length !== words.length) return false;
const c2w = new Map();
const w2c = new Map();
for (let i = 0; i < p.length; i++) {
const c = p[i];
const w = words[i];
if (c2w.has(c) && c2w.get(c) !== w) return false;
if (w2c.has(w) && w2c.get(w) !== c) return false;
c2w.set(c, w);
w2c.set(w, c);
}
return true;
}
// Example usage
const p = "abba";
const s = "dog cat cat dog";
console.log(wordPattern(p, s));
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.