# Word Pattern LeetCode Solution

Difficulty Level Medium
BoltViews 32

## Problem Statement

Word Pattern LeetCode Solution – We are given 2 strings – “s” and “pattern”, we need to find if the pattern follows s. Follows here means full match. More formally, we can for every pattern[i] there should only be one s[i] and vice versa i.e. there is a bijection between a letter in a pattern and a non-empty word in s.

## Examples and Explanation

Example 1:

```Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
a -> dog
b -> cat```

Example 2:
```Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation:
a -> dog
b -> cat
pattern = a which corresponds to s, dog defined earlier, but s has no dog```

Example 3:
```Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Explanation:
a -> dog
Two different a are defined, i.e. dog and cat```

## Approach

We will map the words in s to their corresponding letters in the pattern. If pattern[i] already exists, then check if s[i] is equal to pattern[i]. To map pattern[i] and worlds in “s”, let’s use hashmaps.

Since the words are given through a single string s, we can define another array of strings to store all the words for easy implementation. Iterate through the string s, if there is space, push the word into our string array.

## Code

### C++ Code for Word Pattern LeetCode

```class Solution {
public:
bool wordPattern(string pattern, string s) {
map<char,string> cnt;
vector<string> words;
string t="";
for(int i=0; i<=s.size(); i++) {
if(s[i] == '\0') {
words.push_back(t);
break;
}
else if(s[i] == ' ') {
words.push_back(t);
t="";
}
else t+=s[i];

}

if(words.size() != pattern.size()) return 0;

map<string, int> vis; // vis = visited
for(int i=0; i<pattern.size(); i++) {
if(cnt.find(pattern[i]) != cnt.end()) {
if(cnt[pattern[i]] != words[i]) return 0;

}
else {
cnt[pattern[i]] =  words[i];
if(vis[words[i]]) return 0;
vis[words[i]] = 1;
}
}
return 1;
}
};```

### Java Code for Word Pattern LeetCode

```class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character,String> m=new HashMap<>();
String words[]=s.split(" ");

if(pattern.length()!=words.length) return false;

int n = words.length;
for(int i=0;i<n;i++){

char c= pattern.charAt(i);

if(m.containsKey(c)){
if(!words[i].equals(m.get(c))) return false;
}
else{
if(m.containsValue(words[i])){
return false;
}
m.put(c, words[i]);
}
}
return true;
}
}```

## Complexity Analysis for Word Pattern LeetCode Solution

• Time complexity: O(N)
• Space complexity: O(M)
• M represents the number of unique words in s. Although there are 2 hashmaps there can be at most 26 keys, hence space complexity of the map is constant.
Translate »