# Word Pattern
**Difficulty:** EASY
[External](https://leetcode.com/problems/word-pattern)
Canonical: https://scaleengineer.com/dsa/problems/word-pattern
**Data structures:** Hash Table, String
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Google](https://scaleengineer.com/companies/google), [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
Given a `pattern` and a string `s`, find if `s` follows the same pattern.

Here **follow** means a full match, such that there is a bijection between a letter in `pattern` and a **non-empty** word in `s`. Specifically:

* Each letter in `pattern` maps to **exactly** one unique word in `s`.
* Each unique word in `s` maps to **exactly** one letter in `pattern`.
* No two letters map to the same word, and no two words map to the same letter.

**Example 1:**

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

**Output:** true

**Explanation:**

The bijection can be established as:

* `'a'` maps to `"dog"`.
* `'b'` maps to `"cat"`.

**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:**

* `1 <= pattern.length <= 300`
* `pattern` contains only lower-case English letters.
* `1 <= s.length <= 3000`
* `s` contains only lowercase English letters and spaces `' '`.
* `s` **does not contain** any leading or trailing spaces.
* All the words in `s` are separated by a **single space**.

# Approaches
## Using Two HashMaps
We can solve this problem using two HashMaps to maintain the bijection between pattern characters and words in the string.
**Time:** O(n + k) where n is the length of the pattern and k is the length of the string s (including the split operation) · **Space:** O(n) where n is the number of unique characters/words
**Pros:** Simple and straightforward implementation; Easy to understand and maintain; Good for small to medium sized inputs
**Cons:** Uses extra space for two HashMaps; Requires splitting the string which takes additional time; Not the most memory-efficient solution
### Explanation
This approach uses two HashMaps to track the mapping between pattern characters and words. We first split the string into words and check if the length matches the pattern length. Then, we use one HashMap to store character to word mapping and another for word to character mapping. For each position, we check if the current mappings are consistent.

```java
public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) {
        return false;
    }
    
    Map<Character, String> charToWord = new HashMap<>();
    Map<String, Character> wordToChar = new HashMap<>();
    
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        String word = words[i];
        
        if (!charToWord.containsKey(c)) {
            if (wordToChar.containsKey(word)) {
                return false;
            }
            charToWord.put(c, word);
            wordToChar.put(word, c);
        } else {
            if (!charToWord.get(c).equals(word)) {
                return false;
            }
        }
    }
    
    return true;
}
```
### Algorithm
1. Split the input string into words
2. Check if pattern length equals words length
3. Create two HashMaps:
   - One for character to word mapping
   - One for word to character mapping
4. Iterate through pattern and words simultaneously:
   - If character not mapped, check if word is already mapped
   - If character is mapped, verify mapping is consistent
5. Return true if all mappings are consistent

## Single HashMap with Index Mapping
We can optimize the space usage by using a single HashMap and storing the first occurrence index of both pattern characters and words.
**Time:** O(n + k) where n is the length of the pattern and k is the length of the string s (including the split operation) · **Space:** O(n) where n is the number of unique characters/words, but with a smaller constant factor than the two HashMaps approach
**Pros:** Uses less space compared to two HashMaps approach; More elegant solution; Handles both character and word mappings in a single data structure
**Cons:** Slightly less intuitive than the two HashMaps approach; Still requires splitting the string; May be harder to modify for different requirements
### Explanation
This approach uses a single HashMap to store the first occurrence indices. We can compare the indices of pattern characters and words to determine if they follow the same pattern. This eliminates the need for two separate mappings.

```java
public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) {
        return false;
    }
    
    Map<Object, Integer> map = new HashMap<>();
    
    for (int i = 0; i < words.length; i++) {
        // Use Integer.valueOf(pattern.charAt(i)) to store char as Object
        // and words[i] as Object in the same map
        if (map.put(pattern.charAt(i), i) != map.put(words[i], i)) {
            return false;
        }
    }
    
    return true;
}
```
### Algorithm
1. Split the input string into words
2. Check if pattern length equals words length
3. Create a single HashMap to store indices
4. Iterate through pattern and words:
   - Store and compare first occurrence indices
   - If indices don't match, return false
5. Return true if all indices match

# Solutions
### CSharp

```csharp
public class Solution { public bool WordPattern ( string pattern , string s ) { var ws = s . Split ( ' ' ); if ( pattern . Length != ws . Length ) { return false ; } var d1 = new Dictionary < char , string >(); var d2 = new Dictionary < string , char >(); for ( int i = 0 ; i < ws . Length ; ++ i ) { var a = pattern [ i ]; var b = ws [ i ]; if ( d1 . ContainsKey ( a ) && d1 [ a ] != b ) { return false ; } if ( d2 . ContainsKey ( b ) && d2 [ b ] != a ) { return false ; } d1 [ a ] = b ; d2 [ b ] = a ; } return true ; } }
```

### Java

```java
class Solution { public boolean wordPattern ( String pattern , String s ) { String [] ws = s . split ( " " ); if ( pattern . length () != ws . length ) { return false ; } Map < Character , String > d1 = new HashMap <>(); Map < String , Character > d2 = new HashMap <>(); for ( int i = 0 ; i < ws . length ; ++ i ) { char a = pattern . charAt ( i ); String b = ws [ i ]; if (! d1 . getOrDefault ( a , b ). equals ( b ) || d2 . getOrDefault ( b , a ) != a ) { return false ; } d1 . put ( a , b ); d2 . put ( b , a ); } return true ; } }
```

### CPP

```cpp
class Solution { public: bool wordPattern ( string pattern , string s ) { istringstream is ( s ); vector < string > ws ; while ( is >> s ) { ws . push_back ( s ); } if ( pattern . size () != ws . size ()) { return false ; } unordered_map < char , string > d1 ; unordered_map < string , char > d2 ; for ( int i = 0 ; i < ws . size (); ++ i ) { char a = pattern [ i ]; string b = ws [ i ]; if (( d1 . count ( a ) && d1 [ a ] != b ) || ( d2 . count ( b ) && d2 [ b ] != a )) { return false ; } d1 [ a ] = b ; d2 [ b ] = a ; } return true ; } };
```

### Python

```python
''' >>> p = "abba" >>> s = "dog cat cat dog".split() >>> s ['dog', 'cat', 'cat', 'dog'] >>> zip(p,s) [('a', 'dog'), ('b', 'cat'), ('b', 'cat'), ('a', 'dog')] >>> set(zip(p,s)) set([('b', 'cat'), ('a', 'dog')]) >>> >>> >>> s = "dog dog dog dog".split() # then false for: len(set(pattern)) == len(set(str)) >>> zip(p,s) [('a', 'dog'), ('b', 'dog'), ('b', 'dog'), ('a', 'dog')] >>> set(zip(p,s)) set([('a', 'dog'), ('b', 'dog')]) ''' class Solution ( object ): def wordPattern ( self , pattern , s ): """ :type pattern: str :type s: str :rtype: bool """ s = s . split () a = zip ( pattern , s ) return len ( pattern ) == len ( s ) and len ( set ( a )) == len ( set ( pattern )) == len ( set ( s )) ############ class Solution : def wordPattern ( self , pattern : str , s : str ) -> bool : s = s . split ( ' ' ) n = len ( pattern ) if n != len ( s ): return False c2str , str2c = defaultdict (), defaultdict () for i in range ( n ): k , v = pattern [ i ], s [ i ] if k in c2str and c2str [ k ] != v : return False if v in str2c and str2c [ v ] != k : return False c2str [ k ], str2c [ v ] = v , k return True
```