You are given a pattern string (consisting of lowercase letters) and a sentence string made of words separated by spaces.

Your task:

Determine whether the sentence follows the same pattern, meaning:

• Each character in the pattern maps to exactly one word
• Each word maps to exactly one character
• Mapping must be consistent throughout
• Order must match

Example:

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

Output: true

Another example:

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

Output: false

Another:

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

Output: false

Another:

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

Output: false

---

Problem Understanding

This problem is about bijective mapping:

For the pattern to match:

1. Characters must map consistently to words a → dog b → cat a must map to dog again later
2. Words cannot map to multiple characters a → dog b cannot also map to dog
3. Lengths must align pattern length == number of words

---

Logic Explained in Simple English

Here’s the clean way to think about solving it:

1. Split the sentence into words.
2. If number of words doesn’t equal pattern length → return false.
3. Maintain two mappings:
   • charToWord: pattern character → word
   • wordToChar: word → pattern character
4. Loop through pattern and words in parallel:
   • If character already mapped, ensure it matches this word
   • If word already mapped, ensure it maps back to same character
   • If both unmapped, create mapping
5. If any rule breaks, return false
6. If loop finishes without conflict, return true

Why two maps?

• One map ensures consistency forward
• The other ensures reverse uniqueness
• Together enforce bijection

---

Step-by-Step Approach

1. Split input string s using space
2. If lengths mismatch → false
3. Initialize HashMap<Character, String>
4. Initialize HashMap<String, Character>
5. Loop index i:
   • current pattern char = pattern.charAt(i)
   • current word = words[i]
   • If char exists in map:
     • if mapped word != current word → false
   • If word exists in reverse map:
     • if mapped char != current char → false
   • Else create both mappings
6. Return true

---

Java Implementation

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        
        if (words.length != pattern.length()) {
            return false;
        }
        
        Map<Character, String> charToWord = new HashMap<>();
        Map<String, Character> wordToChar = new HashMap<>();
        
        for (int i = 0; i < pattern.length(); i++) {
            char ch = pattern.charAt(i);
            String word = words[i];
            
            if (charToWord.containsKey(ch)) {
                if (!charToWord.get(ch).equals(word)) {
                    return false;
                }
            } else {
                if (wordToChar.containsKey(word)) {
                    return false;
                }
                charToWord.put(ch, word);
                wordToChar.put(word, ch);
            }
        }
        
        return true;
    }
}

---

Dry Run Example

Input:

pattern = "abba"
s = "dog cat cat dog"

Step through:

words = [“dog”,”cat”,”cat”,”dog”]

i=0:
ch=’a’, word=”dog”
maps created:
a → dog
dog → a

i=1:
ch=’b’, word=”cat”
maps created:
b → cat
cat → b

i=2:
ch=’b’, word=”cat”
charToWord[b] == “cat” → OK
wordToChar[“cat”] == ‘b’ → OK

i=3:
ch=’a’, word=”dog”
charToWord[a] == “dog” → OK
wordToChar[“dog”] == ‘a’ → OK

End of loop → return true

---

Time and Space Complexity

Time Complexity

O(n)

Where n = number of words (or pattern length)

Space Complexity

O(n)

In worst case storing all mappings

---

Common Mistakes and How to Avoid Them

Mistake 1: Using only one map

Fails cases where different chars map to same word.

Mistake 2: Not checking length mismatch early

Leads to false positives.

Mistake 3: Comparing string references instead of values

Must use .equals().

Mistake 4: Ignoring repeated word constraint

Words must map uniquely.

Mistake 5: Splitting incorrectly (multiple spaces)

Using split(" ") is correct per problem constraints.