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 <= 300patterncontains only lower-case English letters.1 <= s.length <= 3000scontains only lowercase English letters and spaces' '.sdoes not contain any leading or trailing spaces.- All the words in
sare 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;
}
Input
pattern = "abba", s = "dog cat cat dog"
Output
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();
}
};
Input
pattern = "abba", s = "dog cat cat dog"
Output
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());
}
}
Input
pattern = "abba", s = "dog cat cat fish"
Output
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
};
Input
pattern = "abba", s = "dog cat cat fish"
Output
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
Input
pattern = "aaaa", s = "dog cat cat dog"
Output
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;
}
}
}
Input
pattern = "aaaa", s = "dog cat cat dog"
Output
false