Hello guys! Welcome back to the Leetcode Daily series. I apologize for the inconsistent blogs, I've been busy moving to a new city for my first-ever in-office internship! Wish me luck, tomorrow's my first day!
We have a very simple problem ahead of us today which will illustrate the applications of a hash table.
Let's begin!
Understanding the Problem
Let's take a look at the problem description.
Given a
patternand a strings, find ifsfollows the same pattern.Here follow means a full match, such that there is a bijection between a letter in
patternand a non-empty word ins.Example 1:
Input: pattern = "abba", s = "dog cat cat dog" Output: trueExample 2:
Input: pattern = "abba", s = "dog cat cat fish" Output: falseExample 3:
Input: pattern = "aaaa", s = "dog cat cat dog" Output: false
The problem seems very simple at first look and honestly, it is. The first idea that you get in your head will be to associate each character in the pattern with a word in the string. And that's it! That's all we need to do to solve this problem.
Intuition
Let's go over a brief description of what exactly a hash table is. A hash table is a data structure that maps keys to values for highly efficient lookups. Usually, an array or a linked list is used for the storage of these values. A hash function is used to make sure a near-constant time complexity lookup is maintained.
To insert a key and value in a hash table, the following steps are carried out:
Compute the key's hash code, which is usually an
intorlongvalue. This hash code is the output provided by the hash function. Two different keys could have the same hash code.Map the hash code to an index in the array. This could be done with something like
index = hash(key) % length(array).At this index, there is a linked list of key-value pairs. The new key-value pair is added to this linked list. Note that we have to use a linked list because there could be collisions, that is, two different keys could have the same hash code, or two different hash codes could have the same index.
To retrieve a value for a given key, its corresponding index is calculated and the linked list at that index is traversed until the required key is found. In case of a large number of collisions, the time complexity of this operation could reach O(n).
This is basically how a hash table works. If the number of collisions is reduced as much as possible, a near-constant lookup, O(1), can be provided.
Let's get back to the problem at hand now.
Here, we need to maintain two mappings: one, that of the characters in the pattern to the corresponding words in the string, and two, that of the words in the string to the corresponding characters in the pattern. Basically, we need to check that each character in the pattern maps to the same word in the string and vice versa.
Let's take a look at the solution now.
Coding Up the Solution
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<string,string> m;
vector<string> words;
string t = "";
s.push_back(' ');
//first, let's construct an array of strings from the given space separated string, where each element will be a word
for(char i : s){
if(i == ' '){
words.push_back(t);
t = "";
}else{
t.push_back(i);
}
}
//if the size of the constructed array of words does not match the length of the pattern string, we can return false here itself
if(words.size() != pattern.length()) return false;
//check the pattern -> word mapping
for(int i = 0; i < pattern.size(); i++){
if(m.find(to_string(pattern[i])) == m.end()){
m[to_string(pattern[i])] = words[i];
}
else{
if(m[to_string(pattern[i])] != words[i]) return false;
}
}
//check the word -> pattern mapping
for(int i = 0; i < words.size(); i++){
if(m.find(words[i]) == m.end()){
m[words[i]] = to_string(pattern[i]);
}
else{
if(m[words[i]] != to_string(pattern[i])) return false;
}
}
return true;
}
};
The code is pretty simple to understand. There are two important steps in the solution.
Checking the pattern -> word mapping: Here, we check if the pattern-to-word mapping is consistent in the given pattern and string. Basically, we're checking that the same character in the pattern maps to the same word in the string.
Checking the word -> pattern mapping: Here, we check if the word-to-pattern mapping is consistent in the given pattern and string. We're checking that the same word in the string maps to the same character in the pattern.
If the C++ map syntax seems unfamiliar to you, check out the links at the end of this article for a refresher!
That's it for today, hope you understood the problem and had a bit of fun learning about hash tables as well. Hash table is a huge topic and I've only provided a very brief summary of what they are. In case your curiosity bug is squirming, check out the next section for more information on hash tables.
Cheers!