Imagine you have a pattern described by a string pattern and another string s composed of words separated by spaces. Your task is to determine if the string s follows the pattern described by pattern.
To "follow the pattern" means:
Each letter in pattern should map to a unique word in s.
Each unique word in s should map to exactly one letter in pattern.
No two letters in pattern should map to the same word, and no two words in s should map to the same letter.
In simpler terms, you need to check if you can assign each letter in pattern to a word in s such that the pattern is consistently followed.
Input: pattern = "abba" , s = "dog cat cat dog"
Output: true
Input: pattern = "abba" , s = "dog cat cat fish"
Output: false
Input: pattern = "aaaa" , s = "dog cat cat dog"
Output: false
The length of pattern is between 1 and 300.
The string s has a length between 1 and 3000 and contains words separated by single spaces.
function wordPattern_HashMaps(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const mapPatternToWord = new Map();
const mapWordToPattern = new Map();
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (mapPatternToWord.get(char) !== word && mapPatternToWord.has(char)) {
return false;
}
if (mapWordToPattern.get(word) !== char && mapWordToPattern.has(word)) {
return false;
}
mapPatternToWord.set(char, word);
mapWordToPattern.set(word, char);
}
return true;
}
const pattern1 = "abba";
const s1 = "dog cat cat dog";
wordPattern_HashMaps(pattern1,s1); //output: true
const pattern2 = "abba";
const s2 = "dog cat cat fish";
wordPattern_HashMaps(pattern2,s2); //output: false
const pattern3 = "aaaa";
const s3 = "dog cat cat dog";
wordPattern_HashMaps(pattern3,s3); //output: false
function wordPattern_TwoPass(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const patternMap = new Map();
const wordMap = new Map();
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (patternMap.has(char)) {
if (patternMap.get(char) !== word) return false;
} else {
patternMap.set(char, word);
}
if (wordMap.has(word)) {
if (wordMap.get(word) !== char) return false;
} else {
wordMap.set(word, char);
}
}
return true;
}
const pattern1 = "abba";
const s1 = "dog cat cat dog";
wordPattern_TwoPass(pattern1,s1); //output: true
const pattern2 = "abba";
const s2 = "dog cat cat fish";
wordPattern_TwoPass(pattern2,s2); //output: false
const pattern3 = "aaaa";
const s3 = "dog cat cat dog";
wordPattern_TwoPass(pattern3,s3); //output: false
function wordPattern_SingleMapEncoding(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const map = new Map();
const encodedPattern = [];
const encodedWords = [];
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (!map.has(char)) map.set(char, word);
encodedPattern.push(map.get(char));
encodedWords.push(word);
}
return encodedPattern.join(' ') === encodedWords.join(' ');
}
const pattern1 = "abba";
const s1 = "dog cat cat dog";
wordPattern_SingleMapEncoding(pattern1,s1); //output: true
const pattern2 = "abba";
const s2 = "dog cat cat fish";
wordPattern_SingleMapEncoding(pattern2,s2); //output: false
const pattern3 = "aaaa";
const s3 = "dog cat cat dog";
wordPattern_SingleMapEncoding(pattern3,s3); //output: false
function wordPattern_Regex(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const map = {};
let regexPattern = '';
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (map[char] && map[char] !== word) return false;
if (!map[char]) map[char] = word;
regexPattern += (i === 0 ? '' : '|') + `(${word})`;
}
const regex = new RegExp(`^${regexPattern}$`);
return regex.test(s);
}
const pattern1 = "abba";
const s1 = "dog cat cat dog";
wordPattern_Regex(pattern1,s1); //output: true
const pattern2 = "abba";
const s2 = "dog cat cat fish";
wordPattern_Regex(pattern2,s2); //output: false
const pattern3 = "aaaa";
const s3 = "dog cat cat dog";
wordPattern_Regex(pattern3,s3); //output: false
function wordPattern_EncodedStrings(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const map = new Map();
let patternString = '';
let wordString = '';
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (!map.has(char)) map.set(char, word);
patternString += map.get(char);
wordString += word;
}
return patternString === wordString;
}
const pattern1 = "abba";
const s1 = "dog cat cat dog";
wordPattern_EncodedStrings(pattern1,s1); //output: true
const pattern2 = "abba";
const s2 = "dog cat cat fish";
wordPattern_EncodedStrings(pattern2,s2); //output: false
const pattern3 = "aaaa";
const s3 = "dog cat cat dog";
wordPattern_EncodedStrings(pattern3,s3); //output: false
function wordPattern_CombinedString(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const patternMap = new Map();
const wordMap = new Map();
let encodedPattern = '';
let encodedWords = '';
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (!patternMap.has(char)) {
patternMap.set(char, i);
encodedPattern += i + '-';
} else {
encodedPattern += patternMap.get(char) + '-';
}
if (!wordMap.has(word)) {
wordMap.set(word, i);
encodedWords += i + '-';
} else {
encodedWords += wordMap.get(word) + '-';
}
}
return encodedPattern === encodedWords;
}
const pattern1 = "abba";
const s1 = "dog cat cat dog";
wordPattern_CombinedString(pattern1,s1); //output: true
const pattern2 = "abba";
const s2 = "dog cat cat fish";
wordPattern_CombinedString(pattern2,s2); //output: false
const pattern3 = "aaaa";
const s3 = "dog cat cat dog";
wordPattern_CombinedString(pattern3,s3); //output: false