Symbol Pattern Verification — Problem Statement & Solution Guide
Problem Description
Given a pattern string P composed of arbitrary characters and a sentence string S containing words separated by single spaces, determine whether S follows the exact ordering dictated by P. Each distinct character in P must map to exactly one distinct word in S, and each word must be mapped from exactly one character (bijection). Return true if such a one‑to‑one correspondence exists; otherwise, return false. The function should accept two parameters—pattern (string) and sentence (string)—and output a boolean value.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Symbol Pattern Verification"
WHY DOES IT MATTER?
Detecting a perfect bijection between symbols and words is a canonical example of constraint satisfaction that appears in template engines, routing tables, and configuration validation, where each placeholder must uniquely bind to a concrete value.
OPTIMIZATION CHALLENGE
The key insight is to enforce both directions of the mapping simultaneously using two hash tables, which collapses what could be a quadratic verification into a single linear scan.
REAL-WORLD CONNECTION
Think of a DNS server mapping hostnames (characters) to IP addresses (words) where each name must resolve to a unique address and vice‑versa; any collision breaks the system, mirroring the bijection requirement.
During an interview, instantiate both maps early, update them in lockstep, and return false the moment a mismatch is detected – this early exit often saves you from writing extra loops.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem reduces to checking a bijective relationship between the characters of pattern P and the words of sentence S. A naïve solution might compare each character to every word, leading to O(|P|·|S|) time, which quickly becomes prohibitive for long inputs. The optimal paradigm leverages hashing (or a dictionary) to store two one‑to‑one mappings: character→word and word→character, guaranteeing constant‑time look‑ups and a single linear pass over the inputs. This dual‑hash approach eliminates duplicate scans and ensures that both the forward and reverse constraints of a bijection are satisfied, yielding O(n) time and O(k) auxiliary space, where n is the number of tokens and k the number of distinct symbols.
Interview Questions on This Problem
Q1How would you modify the solution if the pattern allowed a character to map to multiple consecutive words (e.g., "a" → "dog cat")?
Introduce a backtracking DFS that tries all possible word‑segment lengths for each pattern character while maintaining a map of assignments; prune when a mapping violates previously established bijections, resulting in exponential worst‑case but correct handling of variable‑length segments.
Q2What is the time‑space trade‑off when using a single hash map versus two hash maps for this problem?
A single map can detect forward conflicts but cannot guarantee the reverse uniqueness, potentially requiring an additional set to track used words; using two maps incurs O(k) extra space but simplifies validation to O(1) per token, which is usually preferred.
Q3In a distributed micro‑service that validates user‑defined templates against input strings, how would you ensure the pattern‑checking logic scales horizontally?
Statelessly expose the validation as an API that receives P and S, performs the O(n) hash‑map check, and returns the result; because the algorithm uses only local memory and no shared state, it can be replicated across instances behind a load balancer for linear scalability.
Examples
Input
pattern = "abba", sentence = "dog cat cat dog"
Output
true
Explanation: Map 'a'→"dog" and 'b'→"cat". The pattern expands to "dog cat cat dog", which matches the sentence exactly, and the mapping is bijective.
Input
pattern = "abcd", sentence = "apple banana apple banana"
Output
false
Explanation: The pattern requires four distinct symbols, but the sentence provides only two distinct words. Since 'a' and 'c' would both map to "apple" and 'b' and 'd' to "banana", the mapping is not one‑to‑one, so the result is false.
Input
pattern = "xyzx", sentence = "one two three one"
Output
true
Explanation: Assign 'x'→"one", 'y'→"two", 'z'→"three". The pattern expands to "one two three one", which equals the sentence, and each symbol maps to a unique word, satisfying bijection.
Constraints
- 1 <= pattern.length <= 10^4
- 1 <= number of words in sentence <= 10^4
- All characters in pattern are printable ASCII
- Words in sentence consist of lowercase English letters only
- The total length of sentence does not exceed 10^5 characters
Optimal Approach & Strategy
Use two hash maps to record the forward and reverse mappings while traversing the pattern and words once, aborting early on any conflict. This yields a linear‑time solution with minimal extra space.
Brute Force Approach
Iterate over every character‑word pair and for each pair scan the entire pattern and sentence to verify consistency, resulting in quadratic time. This repeats work for already‑checked positions and quickly exceeds time limits on large inputs.
Verified Code Solutions
function followsPattern(pattern, sentence){
const words = sentence.split(' ');
if(pattern.length!==words.length) return false;
const p2w = new Map();
const w2p = new Map();
for(let i=0;i<pattern.length;i++){
const c = pattern[i];
const w = words[i];
if(p2w.has(c)){
if(p2w.get(c)!==w) return false;
}else{
p2w.set(c,w);
}
if(w2p.has(w)){
if(w2p.get(w)!==c) return false;
}else{
w2p.set(w,c);
}
}
return true;
}
const readline = require('readline');
const rl = readline.createInterface({input:process.stdin,output:process.stdout});
let lines=[];
rl.on('line',line=>{lines.push(line);if(lines.length===2)rl.close();});
rl.on('close',()=>{
const pattern=lines[0];
const sentence=lines[1];
console.log(followsPattern(pattern,sentence)?'true':'false');
});#include <bits/stdc++.h>
using namespace std;
bool followsPattern(const string& pattern, const string& sentence){
vector<string> words;
string word;
stringstream ss(sentence);
while(ss>>word) words.push_back(word);
if(pattern.size()!=words.size()) return false;
unordered_map<char,string> p2w;
unordered_map<string,char> w2p;
for(size_t i=0;i<pattern.size();++i){
char c=pattern[i];
const string& w=words[i];
if(p2w.count(c)){
if(p2w[c]!=w) return false;
}else{
p2w[c]=w;
}
if(w2p.count(w)){
if(w2p[w]!=c) return false;
}else{
w2p[w]=c;
}
}
return true;
}
int main(){
string pattern, sentence;
getline(cin, pattern);
getline(cin, sentence);
cout<<(followsPattern(pattern,sentence)?"true":"false");
return 0;
}
import java.io.*;
import java.util.*;
public class Main{
public static boolean followsPattern(String pattern, String sentence){
String[] words = sentence.split(" ");
if(pattern.length()!=words.length) return false;
Map<Character,String> p2w = new HashMap<>();
Map<String,Character> w2p = new HashMap<>();
for(int i=0;i<pattern.length();i++){
char c = pattern.charAt(i);
String w = words[i];
if(p2w.containsKey(c)){
if(!p2w.get(c).equals(w)) return false;
}else{
p2w.put(c,w);
}
if(w2p.containsKey(w)){
if(w2p.get(w)!=c) return false;
}else{
w2p.put(w,c);
}
}
return true;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String pattern = br.readLine();
String sentence = br.readLine();
System.out.println(followsPattern(pattern, sentence));
}
}
import sys
def follows_pattern(pattern, sentence):
words = sentence.split()
if len(pattern) != len(words):
return False
p2w = {}
w2p = {}
for c, w in zip(pattern, words):
if c in p2w:
if p2w[c] != w:
return False
else:
p2w[c] = w
if w in w2p:
if w2p[w] != c:
return False
else:
w2p[w] = c
return True
if __name__ == "__main__":
data = sys.stdin.read().splitlines()
if len(data) >= 2:
pattern = data[0]
sentence = data[1]
print(str(follows_pattern(pattern, sentence)).lower())
function followsPattern(pattern, sentence){
const words = sentence.split(' ');
if(pattern.length!==words.length) return false;
const p2w = new Map();
const w2p = new Map();
for(let i=0;i<pattern.length;i++){
const c = pattern[i];
const w = words[i];
if(p2w.has(c)){
if(p2w.get(c)!==w) return false;
}else{
p2w.set(c,w);
}
if(w2p.has(w)){
if(w2p.get(w)!==c) return false;
}else{
w2p.set(w,c);
}
}
return true;
}
const readline = require('readline');
const rl = readline.createInterface({input:process.stdin,output:process.stdout});
let lines=[];
rl.on('line',line=>{lines.push(line);if(lines.length===2)rl.close();});
rl.on('close',()=>{
const pattern=lines[0];
const sentence=lines[1];
console.log(followsPattern(pattern,sentence)?'true':'false');
});
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.