290. Word Pattern

Intuition

The problem requires determining if a string s follows the same pattern as given by pattern. This means there should be a one-to-one correspondence (bijection) between each character in pattern and a non-empty word in s.

Approach

1. Split s into Words: First, split the string s into individual words.
2. Length Check: Check if the number of words matches the length of pattern. If they do not match, return false as it's not possible to have a bijection.
3. Mapping Creation: Use two dictionaries to create mappings: - One dictionary to map characters from pattern to words from s. - Another dictionary to map words from s to characters from pattern.
4. Iterate and Map: Iterate through each character in pattern and the corresponding word in s: - Check if the current character in pattern is already mapped to a different word. - Check if the current word in s is already mapped to a different character. - If there are any conflicts in the mappings, return false. - If there are no conflicts, create the mappings in both dictionaries.
5. Return True: If all character-word pairs are processed without conflicts, return true.

This approach ensures that there is a one-to-one correspondence between each character in pattern and each word in s, thereby determining if s follows the same pattern.

Complexity

Time Complexity

• Splitting the string s into words takes O(n) time, where n is the length of s.
• Iterating through the characters of pattern and words of s takes O(m) time, where m is the length of pattern.

Overall time complexity is O(n + m).

Space Complexity

• The space complexity is O(k) where k is the number of unique characters in pattern and unique words in s. This is because the dictionaries will hold at most k key-value pairs.

Code

C++

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map pToStr;
        unordered_map strToP;
        vector words;
        stringstream ss(s);
        string word;
        while (ss >> word) {
            words.push_back(word);
        }
        if (words.size() != pattern.size()) {
            return false;
        }
        for (int i = 0; i < pattern.size(); ++i) {
            char pChar = pattern[i];
            string w = words[i];
            if (pToStr.count(pChar) && pToStr[pChar] != w) {
                return false;
            }
            if (strToP.count(w) && strToP[w] != pChar) {
                return false;
            }
            pToStr[pChar] = w;
            strToP[w] = pChar;
        }  
        return true;
    }
};

Python

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        pToStr = {}
        strToP = {}
        words = s.split()
        if len(words) != len(pattern):
            return False
        for pChar, word in zip(pattern, words):
            # Check if there's a conflict in the mapping from pattern to word
            if pChar in pToStr and pToStr[pChar] != word:
                return False
            # Check if there's a conflict in the mapping from word to pattern
            if word in strToP and strToP[word] != pChar:
                return False
            pToStr[pChar] = word
            strToP[word] = pChar
        return True

Java

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map pToStr = new HashMap<>();
        Map strToP = new HashMap<>();
        String[] words = s.split(" ");
        if (words.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char pChar = pattern.charAt(i);
            String word = words[i];
            // Check if there's a conflict in the mapping from pattern to word
            if (pToStr.containsKey(pChar) && !pToStr.get(pChar).equals(word)) {
                return false;
            }
            if (strToP.containsKey(word) && strToP.get(word) != pChar) {
                return false;
            }
            pToStr.put(pChar, word);
            strToP.put(word, pChar);
        }
        return true;
    }
}

JavaScript

var wordPattern = function(pattern, s) {
    const charToWord = new Map();
    const wordToChar = new Map();
    const words = s.split(' ');
    let i = 0;
    for (const word of words) {
        if (i === pattern.length) {
            return false;
        }
        const currentChar = pattern[i];
        if (!charToWord.has(currentChar) && !wordToChar.has(word)) {
            charToWord.set(currentChar, word);
            wordToChar.set(word, currentChar);
        } else {
            if (charToWord.get(currentChar) !== word || wordToChar.get(word) !== currentChar) {
                return false;
            }
        }
        ++i;
    }
    return i === pattern.length;
};