# 290. Word Pattern

## Description

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.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true


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.

## Solutions

Solution 1: Hash Table

First, we split the string $s$ into a word array $ws$ with spaces. If the length of $pattern$ and $ws$ is not equal, return false directly. Otherwise, we use two hash tables $d_1$ and $d_2$ to record the correspondence between each character and word in $pattern$ and $ws$.

Then, we traverse $pattern$ and $ws$. For each character $a$ and word $b$, if there is a mapping for $a$ in $d_1$, and the mapped word is not $b$, or there is a mapping for $b$ in $d_2$, and the mapped character is not $a$, return false. Otherwise, we add the mapping of $a$ and $b$ to $d_1$ and $d_2$ respectively.

After the traversal, return true.

The time complexity is $O(m + n)$ and the space complexity is $O(m + n)$. Here $m$ and $n$ are the length of $pattern$ and string $s$.

• 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;
}
}

• 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;
}
};

• '''
>>> 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


• func wordPattern(pattern string, s string) bool {
ws := strings.Split(s, " ")
if len(ws) != len(pattern) {
return false
}
d1 := map[rune]string{}
d2 := map[string]rune{}
for i, a := range pattern {
b := ws[i]
if v, ok := d1[a]; ok && v != b {
return false
}
if v, ok := d2[b]; ok && v != a {
return false
}
d1[a] = b
d2[b] = a
}
return true
}

• function wordPattern(pattern: string, s: string): boolean {
const ws = s.split(' ');
if (pattern.length !== ws.length) {
return false;
}
const d1 = new Map<string, string>();
const d2 = new Map<string, string>();
for (let i = 0; i < pattern.length; ++i) {
const a = pattern[i];
const b = ws[i];
if (d1.has(a) && d1.get(a) !== b) {
return false;
}
if (d2.has(b) && d2.get(b) !== a) {
return false;
}
d1.set(a, b);
d2.set(b, a);
}
return true;
}


• 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;
}
}

• use std::collections::HashMap;

impl Solution {
pub fn word_pattern(pattern: String, s: String) -> bool {
let cs1: Vec<char> = pattern.chars().collect();
let cs2: Vec<&str> = s.split_whitespace().collect();
let n = cs1.len();
if n != cs2.len() {
return false;
}
let mut map1 = HashMap::new();
let mut map2 = HashMap::new();
for i in 0..n {
let c = cs1[i];
let s = cs2[i];
if !map1.contains_key(&c) {
map1.insert(c, i);
}
if !map2.contains_key(&s) {
map2.insert(s, i);
}
if map1.get(&c) != map2.get(&s) {
return false;
}
}
true
}
}