Word Pattern

easy

Last Updated - 03/09/2024

Problem Statement Solution 1: Hash Maps for Both Directions Solution 2: Two Pass Solution with String Splitting and Maps Solution 3: Single Map with Pattern Encoding Solution 4: Regular Expression Matching Solution 5: Encoding Pattern and Words to Unique Strings Solution 6: Using a Combined String Encoding for Verification More Problems Solutions

Problem Statement

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.

Example 1

Input: pattern = "abba" , s = "dog cat cat dog"

Output: true

Example 2

Input: pattern = "abba" , s = "dog cat cat fish"

Output: false

Example 3

Input: pattern = "aaaa" , s = "dog cat cat dog"

Output: false

Constraints

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.

Solution 1: Hash Maps for Both Directions

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

Solution 2: Two Pass Solution with String Splitting and Maps

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

Solution 3: Single Map with Pattern Encoding

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

Solution 4: Regular Expression Matching

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

Solution 5: Encoding Pattern and Words to Unique Strings

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

Solution 6: Using a Combined String Encoding for Verification

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