Table of Contents
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[3] = a which corresponds to s[0], dog defined earlier, but s[3] 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++) {
// pattern already exists
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)
- N represents the number of words in s or the number of letters in the pattern
- 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.