hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
290. Word Pattern
Problem: 290. Word Pattern
Problem Link: leetcode.com/problems/word-pattern/
Companies Asked: Bolt, Uber, Adobe, Amazon
Approach:
Declared two unordered_map (HashMap). One for mapping each word to a single character and the other for each character to every single word.
Return false if the total number of words in s is not equal to the total number of characters in the pattern.
Now, while traversing through each word of s and each character from pattern, do the following things -
Firstly, check if both ith character of pattern and word of s has been already assigned with something.
If they are not assigned, then map them bidirectionally (that is word[i] => pattern[i] in a map and pattern[i] => word[i] in another map)
If they are already assigned, then check if word[i] is assigned to pattern[i] and pattern[i] is assigned to word[i].
If not then return false. Otherwise, keep checking for the rest of the words and patterns.
Return true at the end as all of the false cases are covered.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N), N = Length of pattern
Code [C++]
class Solution {
public:
bool wordPattern(string pattern, string s) {
vector<string>words;
stringstream ss(s);
while(ss >> s){
words.push_back(s);
}
int n = pattern.size();
if(n != words.size()) return false;
unordered_map<char, string>mymap;
unordered_map<string, char>checkMap;
for(int i=0; i<n; i++){
if(mymap.find(pattern[i]) == mymap.end() && checkMap.find(words[i]) == checkMap.end()){
mymap[pattern[i]] = words[i];
checkMap[words[i]] = pattern[i];
}
else{
if((mymap[pattern[i]] != words[i]) || checkMap[words[i]] != pattern[i]) return false;
}
}
return true;
}
};