Word Pattern [Easy] — Bijective Two-Way Map

Problem Statement

Return true if s (space-separated words) follows the same pattern as pattern (bijection between chars and words).

Input: pattern="abba", s="dog cat cat dog" → true
Input: pattern="abba", s="dog cat cat fish" → false
Input: pattern="aaaa", s="dog cat cat dog" → false

Solutions

Python

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words): return False
    pw, wp = {}, {}
    for p, w in zip(pattern, words):
        if pw.get(p, w) != w or wp.get(w, p) != p:
            return False
        pw[p] = w; wp[w] = p
    return True

C++

bool wordPattern(string pattern, string s) {
    vector<string> words; stringstream ss(s); string word;
    while(ss>>word) words.push_back(word);
    if(pattern.size()!=words.size()) return false;
    map<char,string> pw; map<string,char> wp;
    for(int i=0;i<pattern.size();i++){
        if(pw.count(pattern[i])&&pw[pattern[i]]!=words[i]) return false;
        if(wp.count(words[i])&&wp[words[i]]!=pattern[i]) return false;
        pw[pattern[i]]=words[i]; wp[words[i]]=pattern[i];
    }
    return true;
}

Java

public boolean wordPattern(String pattern, String s) {
    String[] words=s.split(" ");
    if(pattern.length()!=words.length) return false;
    Map<Character,String> pw=new HashMap<>(); Map<String,Character> wp=new HashMap<>();
    for(int i=0;i<pattern.length();i++){
        char p=pattern.charAt(i); String w=words[i];
        if(pw.containsKey(p)&&!pw.get(p).equals(w)) return false;
        if(wp.containsKey(w)&&wp.get(w)!=p) return false;
        pw.put(p,w); wp.put(w,p);
    }
    return true;
}

Complexity

Time: O(n), Space: O(n)