Symbol Pattern Verification — Problem Statement & Solution Guide
Problem Description
Given a symbol pattern and a sentence, verify if the sentence follows the exact structure of the pattern, where each symbol maps to exactly one word and vice versa.
Examples
Input
pattern = 'abba', sentence = 'dog cat cat dog'
Output
false
Explanation: Step 1: Split the sentence into words. The sentence 'dog cat cat dog' becomes ['dog', 'cat', 'cat', 'dog']. Step 2: Compare the pattern and the words. The pattern 'abba' has 4 characters, and the words have 4 elements. Since the lengths are equal, proceed to the next step. Step 3: Compare each character in the pattern with the corresponding word. The pattern 'abba' has 'a' at index 0, 'b' at index 1, 'b' at index 2, and 'a' at index 3. The words have 'dog' at index 0, 'cat' at index 1, 'cat' at index 2, and 'dog' at index 3. Since 'dog' is not equal to 'a', the function returns false.
Input
pattern = 'abba', sentence = 'dog cat cat fish'
Output
false
Explanation: Step 1: Split the sentence into words. The sentence 'dog cat cat fish' becomes ['dog', 'cat', 'cat', 'fish']. Step 2: Compare the pattern and the words. The pattern 'abba' has 4 characters, and the words have 4 elements. Since the lengths are equal, proceed to the next step. Step 3: Compare each character in the pattern with the corresponding word. The pattern 'abba' has 'a' at index 0, 'b' at index 1, 'b' at index 2, and 'a' at index 3. The words have 'dog' at index 0, 'cat' at index 1, 'cat' at index 2, and 'fish' at index 3. Since 'fish' is not equal to 'a', the function returns false.
Constraints
- 1 <= pattern.length <= 300
- s contains lowercase English letters separated by a single space.
Optimal Approach & Strategy
Split string by space. Use two HashMaps: charToWord and wordToChar. If mappings conflict, return false. Time O(N), Space O(N).
Brute Force Approach
Use nested loops to verify mappings. Time O(N^2).
Verified Code Solutions
function wordPattern(pattern, sentence) { let words = sentence.split(' '); if (pattern.length !== words.length) return false; let map = new Map(); for (let i = 0; i < pattern.length; i++) { if (!map.has(pattern[i])) { if (Array.from(map.values()).includes(words[i])) return false; map.set(pattern[i], words[i]); } else { if (map.get(pattern[i]) !== words[i]) return false; } } return true; }public boolean symbolPatternVerification(String pattern, String sentence) {
if (pattern.length() != sentence.split(" ").length)
return false;
HashMap<Character, String> patternDict = new HashMap<>();
for (int i = 0; i < pattern.length(); i++) {
if (patternDict.containsKey(pattern.charAt(i))) {
if (!patternDict.get(pattern.charAt(i)).equals(sentence.split(" ")[i]))
return false;
} else {
patternDict.put(pattern.charAt(i), sentence.split(" ")[i]);
}
}
return true;
}def symbol_pattern_verification(pattern, sentence):
if len(pattern) != len(sentence.split()):
return False
pattern_dict = {}
for i in range(len(pattern)):
if pattern[i] in pattern_dict:
if pattern_dict[pattern[i]] != sentence.split()[i]:
return False
else:
pattern_dict[pattern[i]] = sentence.split()[i]
return Truefunction wordPattern(pattern, sentence) { let words = sentence.split(' '); if (pattern.length !== words.length) return false; let map = new Map(); for (let i = 0; i < pattern.length; i++) { if (!map.has(pattern[i])) { if (Array.from(map.values()).includes(words[i])) return false; map.set(pattern[i], words[i]); } else { if (map.get(pattern[i]) !== words[i]) return false; } } return true; }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.