Welcome back.
Let's now code the solution to check whether the two given strings are isomorphic.
Now for this, let's write a function and let's call it check isomorphic.
And this function is going to take in the two strings s and t.
So these are the two strings that is given to us.
Now once we are inside this function we are going to check whether the two strings s and t are of the
same length.
So if they are not of the same length, we can just return false.
So let's do that over here.
If s dot length not equal to t dot length.
In that case, we can just return false.
All right.
Now, if they are of equal length, we proceed further.
So we create two hash tables.
So let's say const s hash.
And it's empty at this point.
And we have const t hash.
Which is also empty.
Right.
So we have these two empty objects or the hash tables.
Now we are going to iterate or loop through the given strings.
Right.
So let's say for length let I is equal to zero.
I less than s dot length.
I plus plus.
So we can take any length because both of them are of equal length.
So that's why I'm taking s dot length over here.
Now let's find the character at the ith index in both the strings.
So let's say let char s.
That's the character in string S at index I.
That's S at I.
Similarly, we are going to say let char t is equal to t at I.
So we found the two characters.
All right.
So respectively in string s and string t.
Now we are going to check whether there is an entry for char s in the hash table.
S hash.
All right.
So let's check that.
So let's do that over here.
If.
Not.
That means if there is no entry in S hash.
With the key being chara's, right?
So if it is not there, then we are going to make an entry.
We are going to say s hash.
At char s is equal to char t.
All right.
So that's one way mapping.
So we we have the key as char s and the value is char t.
Now we are going to make a similar mapping in the key hash object or the key hash uh hash table which
we created over here.
So let's check that.
So if not t hash.
Charity.
Right.
So if there if it's undefined, that means there is no entry for char t with key as char t in t hash.
Then we are going to say t hash at char t is equal to char s.
So we have made the entries.
Now we are going to check whether the criteria for the two strings to be isomorphic is fulfilled or
not.
So let's check that over here.
If.
Sash.
At char s if this is not equal to char t, right.
If this is not equal, then it's it's not fulfilled.
So we can return false or if t hash.
At char t is not equal to char s, right.
If this is also not fulfilled if any one of these two right.
So we have these two criterias.
If any of these is not fulfilled then we just return false right.
So the mapping is not isomorphic.
So we return false.
And if we are able to loop through the strings s and t and we don't return false.
Right.
So if we come out of this then we can just return true.
And we are done.
Without function.
All right.
So again let's quickly walk through what we have done over here.
We are checking we are taking the character at the ith index in string s and string t.
Now if there is no entry for this in the HashMap right in.
If there is no entry for char s in S hash, then we are making that entry and the value would be char
t.
That is the character in string t at the ith index.
Similarly, we are doing the same thing over here as well.
So if there is no entry for char t in t hash, then we are making an entry with the value being char
s.
Now, once we have done that we are checking.
So if we made the entry freshly then definitely these two criterias will not be true, right?
So it will not be true.
Therefore we will not return false.
But when we find something which already has an entry, and it is at that point that we are checking
whether the mapping is actually isomorphic, right.
So that is checked over here.
And as we seen in the previous video we are checking both ways.
Right.
So the mapping from char s should be to char t in S hash.
And the mapping should be from char t to char s in t hash.
If either of these mappings is not true, then we return false.
And if we are not able to return false and we come out of the for loop, then we return true.
So that is our function.
Now let's quickly run it and test our function.
So I have checked isomorphic.
So let's just call this function.
And let's just pass a and b.
All right.
So the expectation is that it should be true right.
So A is mapping to B.
So it should be true.
Yes we are getting true.
Now what if the lengths are not the same now it should be false.
Yes it's false.
What if I put B over here again.
It should be false right.
Because A and c is mapping to B which is not allowed.
What if I change this to D then it's true.
Yes.
That's working.
All right.
Now what about having a over here now having B over here.
In this case it should be true.
Yes.
We are getting true.
Now if this was something else for example.
Ah it should be false.
Yes.
So this is working.
Our function is working.
Now let's quickly walk through the code and let's take a sample.
We have the sample over here.
Let's see what's happening over here.
And let's walk through the code.
So let's quickly see what's happening over here.
Now we have a, a c a and b b d are over here right now.
Once we call the function and we are inside the function, we are going to check whether these two are
of equal length.
So that is done over here.
Now we see that both of them are of length four.
So we don't return over here.
And then we come over here right.
So we have this hash over here.
So let's just write that as hash.
And we have to hash over here.
Now, once we are inside the for loop, we are going to loop from I is equal to zero till I is less
than s dot length.
So in this case this is four.
So I will take the value zero, one, two and three.
Now when I is equal to zero we are going to take the character at the zeroth index over here.
That's a and over here that's B.
And we are going to check is there an entry over here.
So at this point these two are empty right.
So these two are empty.
Now at this point we see that's hash at char s.
That is s hash at a.
There is no key a over here.
So we make this entry over here right.
So we put a over here as the key.
And char t which is b is the value.
Similarly we check whether there is an entry for B over here which is not there.
Right.
So we make an entry of B over here.
And the value is char s which is a.
All right.
Now over here because we made these entries right.
These this condition over here will definitely not be true.
Right.
So we don't return false.
Now s hash at char s is equal to char t which is b.
We just made that entry right.
Similarly t hash at char t which is b is equal to a.
We just made that entry.
All right.
So again I becomes one.
Now.
Now we take the values again a and b.
At this point we see that this these two conditions are not true.
Right.
S hash at s is not undefined.
And t hash at char t is not undefined.
So we don't go inside over here.
And then we come over here.
Now we are going to check whether these are equal right.
So s hash a char s.
This is a.
So is that is it having the value b.
So we don't want if it was not b then we would have returned false.
But at this point yes this is mapping to b.
So and we have a map to B over here.
And then we have B mapped to A over here as well.
So we don't return false.
Right.
So again I is incremented I becomes two.
Now we take this we take C and we take D.
Right.
And over here we see that these entries are not there.
So we make that entry c and d and d and C over here.
Right.
And again because we just made the made the entry this will not be true.
We don't return false I is incremented to three.
Again we get A and we get R right.
We get a and we get R.
So when we come over here we see that the entry is there.
Right.
So we don't do it.
It does not go over here.
It does not go in over here.
And when we come over here for R we see that there is no entry.
So we make an entry over here R which is mapped to a at this point.
Now over here we are going to check s hash at char s.
So that is for a right.
So that is equal to b.
But char t at this point is equal to r.
That is what we got right.
This is r.
Therefore these are not equal.
And we will just return false.
And that's how the function works.
So we see that these two are not isomorphic.
Now if we had instead of R if we had b over there then we would have come out of it right.
So again we don't return false.
And then I will become equal to four which is not less than four.
So we come out of it and we would have returned true over here.
All right.
So we have seen how the function works.
Now what about the space and time complexity.
We can see that the space complexity is O of one.
Right.
So this is a bit tricky.
Why is that.
So we are definitely consuming auxiliary space when we make these two hash tables.
Right.
But still the space complexity is O of one.
Because in the question it's mentioned that the two strings S and T consist of valid Ascii characters.
And the important thing is that that's a fixed size, right.
So there are a fixed number of valid Ascii characters.
So the space complexity is O of some constant.
Right.
So we can we can say that that's something like 256 or so.
But whatever number this is just going to be a constant number.
And O of a constant is nothing but O of one.
Right.
So that's why the space complexity of this solution is O of one.
And the time complexity.
When it comes to the time complexity, we can see that we are just looping once, right?
So we just have one for loop.
So the time complexity is O of n just by using this one for loop we are we are looping through the two
given strings.
We are we are having the values from I zero to s dot length minus one.
So we are just going over the characters once.
So that's why the time complexity of this solution is o of n.