Continuing my problem-solving series, this blog will be about another exciting problem that I recently found and solved on LeetCode. This week’s problem is called “Isomorphic Strings” and here is the problem description:
Even though it’s an easy level problem, it’s a pretty popular one among the interviewers at big companies. According to LeetCode’s information, “Isomorphic Strings” was asked during interviews by companies like Google, Amazon, Microsoft, and Facebook at least few times in the last 6 months.
Let’s quickly go over the problem description and try to mark the most important points, that will help us to pass all the test cases from the first try. Okay, so our function, which is called isIsomorphic by default, takes 2 parameters which are strings s and t and we are expected to return a boolean value that represents if these strings are isomorphic. The last two paragraphs are basically explaining in detail what isomorphic means in this case.
If we take a look at Example 3 we can see that character ‘p’ in s is mapped to ‘t’ in t, so whenever we encounter ‘p’ in our s later, t is expected to have ‘t’ at the same position, if not, s and t can’t be isomorphic.
First thing I decided to address in my implementation is the fact that isomorphic strings should be of the same length, in case they are not, we can go ahead and say that they are not isomorphic by returning false:
Only after I was done with this basic edge case, I proceeded to declare variables. And here is where we already need to think about efficiency, this problem can be solved using 1 Object, 2 Objects or an Object and a Set. The first 2 options are not the most efficient ones because they will require 2 for loops and this may cause our program to have up to O(n²) time complexity which is something that we definitely don’t want, this is where Set comes into play. Taking into account the fact that looking up element in a Set is just O(1), we can force our program to have time complexity of O(n) at worst and I’ll show you this, most efficient, way of solving this problem:
check will store the mappings and set will just keep us assured that we are not mapping different characters from the first string to the same character in the second one.
As I mentioned before we will need a for loop, since our s and t are definitely of the same length(we checked it at the very beginning), we can use any of their .length values as loop’s condition. Inside of the loop we will check if the mapping for the character from the first array to the one from the second one is already inside of our check Object, i.e. check already contains a key equal to the character of the first array, if not, we will place it in there and then, the most important part!, we check if we already have a character from the second string in our set, if so, means it was already mapped to another character and we can definitely say that s and t are not isomorphic and return false, otherwise, we add this character to set. One last condition that we need to add is when the character of the first string already exists as a key in check but mapped to another character from the second string, in this case, we return false as well:
This is the for loop I was talking about in the previous paragraph and if we exit out of it without returning false, means that our strings are isomorphic and we can confirm that by returning true:
Here is a full final and most efficient solution that I managed to come up with:
var isIsomorphic = function(s, t) {
if(s.length !== t.length) return false
let check = {}, set = new Set()
for(let i = 0; i < s.length; i++){
if(!check[s[i]]){
check[s[i]] = t[i]
if(set.has(t[i])) return false
set.add(t[i])
}else if(check[s[i]] !== t[i]){
return false
}
}
return true
};If you liked this post, let me know in the replies section and if you know of any better way of solving this problem, I would like to know it too, so don’t hesitate to share it in the same old replies section as well!