Problem Statement

Given a pattern string and a text string containing words separated by spaces, determine if the text folllows the same pattern as the pattern string.

A full match requires a bijection between each character in the pattern and each non-empty word in the text. This means:

• Each character maps to exactly one unique word
• Each word maps back to exactly one unique character
• No two characters map to the same word

Example Cases

Pattern: "abba", Text: "dog cat cat dog" → true
Pattern: "abba", Text: "dog cat cat fish" → false
Pattern: "aaaa", Text: "dog cat cat dog" → false
Pattern: "abba", Text: "dog dog dog dog" → false

Solution Approaches

Approach 1: Brute Force Comparison

This straightforward method compares every pair of positions in the pattern. If two pattern characters are equal, thier corresponding words must be equal. If two pattern characters differ, their corresponding words must also differ.

public bool ValidatePatternBruteForce(string pattern, string input) {
    string[] tokens = input.Split(' ');
    if (pattern.Length != tokens.Length) {
        return false;
    }
    
    for (int i = 0; i < pattern.Length; i++) {
        for (int j = i + 1; j < pattern.Length; j++) {
            if (pattern[i] == pattern[j]) {
                if (tokens[i] != tokens[j]) {
                    return false;
                }
            } else {
                if (tokens[i] == tokens[j]) {
                    return false;
                }
            }
        }
    }
    return true;
}

Approach 2: Optimized Dictionary Tracking

This efficient solution uses a dictionary to store character-to-word mappings and a HashSet to track words that have already been assigned, ensuring O(n) time complexity.

public bool MatchPatternOptimized(string sequence, string phrase) {
    string[] words = phrase.Split(' ');
    if (sequence.Length != words.Length) {
        return false;
    }
    
    Dictionary<char, string> mapping = new Dictionary<char, string>();
    HashSet<string> usedWords = new HashSet<string>();
    
    for (int index = 0; index < sequence.Length; index++) {
        char key = sequence[index];
        string currentWord = words[index];
        
        if (mapping.TryGetValue(key, out string mappedWord)) {
            if (mappedWord != currentWord) {
                return false;
            }
        } else {
            if (usedWords.Contains(currentWord)) {
                return false;
            }
            mapping[key] = currentWord;
            usedWords.Add(currentWord);
        }
    }
    return true;
}