## Algorithm

Problem Name: 290. Word Pattern

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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
bool wordPattern(char* pattern, char* str) {
char *bucket[26] = { 0 };
int   len   [26] = { 0 };
char c, *p, *s;
char t, *pat;
int l;

pat = pattern;
while (*str && *pattern) {
s = str;
l = 0;
while (*str && *str != ' ') {
str ++;
}
l = str - s;
if (*str == ' ') {
*str = 0;  // strcmp is much faster than strncmp, so cut the strings.
str ++;    // skip single space
}

c = *(pattern ++) - 'a';
p = bucket[c];
if (p) {
if (strcmp(p, s)) return false;
} else {
bucket[c] = s;
len[c] = l;
// cannot be same with other pattern
p = pat;
while ((t = (*p ++) - 'a') != c) {
if (len[t] == len[c] &&
!strcmp(bucket[t], bucket[c])) return false;
}
}
}

return (!*pattern && !*str) ? true : false;
}
``````
Copy The Code &

Input

cmd
pattern = "abba", s = "dog cat cat dog"

Output

cmd
true

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_mapc2s;
unordered_map < string, char>s2c;
stringstream ss(str);
string s = "";
int i = 0;
while(ss>>s){
if(i == pattern.size() || c2s.count(pattern[i]) && c2s[pattern[i]] != s || s2c.count(s) && s2c[s] != pattern[i]) return false;
c2s[pattern[i]] = s;
s2c[s] = pattern[i++];
}
return i == pattern.size();
}
};
``````
Copy The Code &

Input

cmd
pattern = "abba", s = "dog cat cat dog"

Output

cmd
true

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean wordPattern(String pattern, String str) {
StringBuilder patternSb = new StringBuilder();
Map < Character, Integer> patternMap = new HashMap<>();
int count = 0;
for (char c : pattern.toCharArray()) {
if (!patternMap.containsKey(c)) {
patternMap.put(c, count++);
}
patternSb.append(patternMap.get(c));
}
StringBuilder strSb = new StringBuilder();
Map < String, Integer> strMap = new HashMap<>();
count = 0;
for (String s : str.split("\\s+")) {
if (!strMap.containsKey(s)) {
strMap.put(s, count++);
}
strSb.append(strMap.get(s));
}
return patternSb.toString().equals(strSb.toString());
}
}
``````
Copy The Code &

Input

cmd
pattern = "abba", s = "dog cat cat fish"

Output

cmd
false

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const wordPattern = function(pattern, str) {
const pm = {}
const sm = {}
const sa = str.trim().split(' ')
if(pattern.length !== sa.length) return false
for(let i = 0; i< pattern.length; i++) {
if(!pm.hasOwnProperty(pattern[i])) {
pm[pattern[i]] = sa[i]
}
if(!sm.hasOwnProperty(sa[i])) {
sm[sa[i]] = pattern[i]
}

if( !(pm[pattern[i]] === sa[i] && sm[sa[i]] === pattern[i] ) > {
return false
}

}
return true
};
``````
Copy The Code &

Input

cmd
pattern = "abba", s = "dog cat cat fish"

Output

cmd
false

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
if len(str.split())!=len(pattern): return False
dic={}
for word in str.split():
if not pattern[0] in dic.values() and not word in dic: dic[word]=pattern[0]
else:
if not word in dic or dic[word]!=pattern[0]: return False
pattern=pattern[1:]
return True
``````
Copy The Code &

Input

cmd
pattern = "aaaa", s = "dog cat cat dog"

Output

cmd
false

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0290_WordPattern
{
public bool WordPattern(string pattern, string str)
{
var words = str.Split();
if (words.Length != pattern.Length) return false;

var map1 = new Dictionary < char, string>();
var map2 = new Dictionary();
for (int i = 0; i  <  pattern.Length; i++)
{
var ch = pattern[i];
if (map1.ContainsKey(ch))
{
if (map1[ch] != words[i])
return false;
}
else
map1[ch] = words[i];

if (map2.ContainsKey(words[i]))
{
if (map2[words[i]] != ch)
return false;
}
else
map2[words[i]] = ch;
}

return true;
}
}
}
``````
Copy The Code &

Input

cmd
pattern = "aaaa", s = "dog cat cat dog"

Output

cmd
false