1 00:00:00,710 --> 00:00:01,790 Welcome back. 2 00:00:01,790 --> 00:00:06,860 Let's now code the solution to check whether the two given strings are isomorphic. 3 00:00:06,860 --> 00:00:11,090 Now for this, let's write a function and let's call it check isomorphic. 4 00:00:12,830 --> 00:00:17,450 And this function is going to take in the two strings s and t. 5 00:00:17,480 --> 00:00:20,510 So these are the two strings that is given to us. 6 00:00:20,540 --> 00:00:27,050 Now once we are inside this function we are going to check whether the two strings s and t are of the 7 00:00:27,050 --> 00:00:27,740 same length. 8 00:00:27,740 --> 00:00:30,740 So if they are not of the same length, we can just return false. 9 00:00:30,740 --> 00:00:32,000 So let's do that over here. 10 00:00:32,000 --> 00:00:36,380 If s dot length not equal to t dot length. 11 00:00:37,620 --> 00:00:40,080 In that case, we can just return false. 12 00:00:41,890 --> 00:00:42,400 All right. 13 00:00:42,400 --> 00:00:45,220 Now, if they are of equal length, we proceed further. 14 00:00:45,220 --> 00:00:47,410 So we create two hash tables. 15 00:00:47,410 --> 00:00:49,420 So let's say const s hash. 16 00:00:50,600 --> 00:00:52,700 And it's empty at this point. 17 00:00:55,750 --> 00:00:57,910 And we have const t hash. 18 00:00:59,900 --> 00:01:01,490 Which is also empty. 19 00:01:01,700 --> 00:01:01,940 Right. 20 00:01:01,940 --> 00:01:05,300 So we have these two empty objects or the hash tables. 21 00:01:05,330 --> 00:01:09,920 Now we are going to iterate or loop through the given strings. 22 00:01:09,920 --> 00:01:10,130 Right. 23 00:01:10,130 --> 00:01:13,040 So let's say for length let I is equal to zero. 24 00:01:14,050 --> 00:01:16,600 I less than s dot length. 25 00:01:17,360 --> 00:01:18,590 I plus plus. 26 00:01:18,590 --> 00:01:21,500 So we can take any length because both of them are of equal length. 27 00:01:21,500 --> 00:01:23,690 So that's why I'm taking s dot length over here. 28 00:01:23,780 --> 00:01:28,250 Now let's find the character at the ith index in both the strings. 29 00:01:28,250 --> 00:01:31,400 So let's say let char s. 30 00:01:32,440 --> 00:01:35,920 That's the character in string S at index I. 31 00:01:35,920 --> 00:01:37,840 That's S at I. 32 00:01:40,640 --> 00:01:46,040 Similarly, we are going to say let char t is equal to t at I. 33 00:01:46,070 --> 00:01:48,020 So we found the two characters. 34 00:01:48,020 --> 00:01:48,470 All right. 35 00:01:48,470 --> 00:01:52,520 So respectively in string s and string t. 36 00:01:52,700 --> 00:01:59,150 Now we are going to check whether there is an entry for char s in the hash table. 37 00:01:59,330 --> 00:01:59,990 S hash. 38 00:01:59,990 --> 00:02:00,320 All right. 39 00:02:00,320 --> 00:02:01,430 So let's check that. 40 00:02:01,430 --> 00:02:03,080 So let's do that over here. 41 00:02:04,070 --> 00:02:04,820 If. 42 00:02:05,660 --> 00:02:06,260 Not. 43 00:02:06,260 --> 00:02:09,470 That means if there is no entry in S hash. 44 00:02:10,150 --> 00:02:13,300 With the key being chara's, right? 45 00:02:13,300 --> 00:02:16,270 So if it is not there, then we are going to make an entry. 46 00:02:16,270 --> 00:02:18,130 We are going to say s hash. 47 00:02:18,940 --> 00:02:22,780 At char s is equal to char t. 48 00:02:24,830 --> 00:02:25,130 All right. 49 00:02:25,130 --> 00:02:27,050 So that's one way mapping. 50 00:02:27,050 --> 00:02:31,370 So we we have the key as char s and the value is char t. 51 00:02:31,400 --> 00:02:39,290 Now we are going to make a similar mapping in the key hash object or the key hash uh hash table which 52 00:02:39,290 --> 00:02:40,190 we created over here. 53 00:02:40,190 --> 00:02:41,570 So let's check that. 54 00:02:41,570 --> 00:02:43,940 So if not t hash. 55 00:02:47,790 --> 00:02:48,570 Charity. 56 00:02:48,660 --> 00:02:49,260 Right. 57 00:02:49,260 --> 00:02:56,580 So if there if it's undefined, that means there is no entry for char t with key as char t in t hash. 58 00:02:56,580 --> 00:03:03,450 Then we are going to say t hash at char t is equal to char s. 59 00:03:03,780 --> 00:03:05,760 So we have made the entries. 60 00:03:05,760 --> 00:03:13,140 Now we are going to check whether the criteria for the two strings to be isomorphic is fulfilled or 61 00:03:13,140 --> 00:03:13,560 not. 62 00:03:13,560 --> 00:03:15,270 So let's check that over here. 63 00:03:15,270 --> 00:03:16,050 If. 64 00:03:17,160 --> 00:03:17,790 Sash. 65 00:03:19,260 --> 00:03:25,950 At char s if this is not equal to char t, right. 66 00:03:25,950 --> 00:03:28,890 If this is not equal, then it's it's not fulfilled. 67 00:03:28,890 --> 00:03:33,120 So we can return false or if t hash. 68 00:03:33,900 --> 00:03:40,080 At char t is not equal to char s, right. 69 00:03:40,110 --> 00:03:43,380 If this is also not fulfilled if any one of these two right. 70 00:03:43,380 --> 00:03:44,970 So we have these two criterias. 71 00:03:44,970 --> 00:03:49,050 If any of these is not fulfilled then we just return false right. 72 00:03:49,560 --> 00:03:51,720 So the mapping is not isomorphic. 73 00:03:51,720 --> 00:03:53,370 So we return false. 74 00:03:53,730 --> 00:03:59,850 And if we are able to loop through the strings s and t and we don't return false. 75 00:03:59,850 --> 00:04:00,240 Right. 76 00:04:00,240 --> 00:04:03,450 So if we come out of this then we can just return true. 77 00:04:04,020 --> 00:04:05,370 And we are done. 78 00:04:07,020 --> 00:04:07,980 Without function. 79 00:04:07,980 --> 00:04:08,430 All right. 80 00:04:08,430 --> 00:04:12,210 So again let's quickly walk through what we have done over here. 81 00:04:13,050 --> 00:04:19,260 We are checking we are taking the character at the ith index in string s and string t. 82 00:04:19,410 --> 00:04:23,400 Now if there is no entry for this in the HashMap right in. 83 00:04:23,400 --> 00:04:29,940 If there is no entry for char s in S hash, then we are making that entry and the value would be char 84 00:04:29,940 --> 00:04:30,210 t. 85 00:04:30,240 --> 00:04:34,020 That is the character in string t at the ith index. 86 00:04:34,020 --> 00:04:36,630 Similarly, we are doing the same thing over here as well. 87 00:04:36,630 --> 00:04:43,530 So if there is no entry for char t in t hash, then we are making an entry with the value being char 88 00:04:43,530 --> 00:04:43,860 s. 89 00:04:43,890 --> 00:04:46,470 Now, once we have done that we are checking. 90 00:04:46,470 --> 00:04:51,990 So if we made the entry freshly then definitely these two criterias will not be true, right? 91 00:04:51,990 --> 00:04:53,130 So it will not be true. 92 00:04:53,130 --> 00:04:54,660 Therefore we will not return false. 93 00:04:54,660 --> 00:05:01,080 But when we find something which already has an entry, and it is at that point that we are checking 94 00:05:01,080 --> 00:05:03,930 whether the mapping is actually isomorphic, right. 95 00:05:03,930 --> 00:05:05,550 So that is checked over here. 96 00:05:05,550 --> 00:05:08,730 And as we seen in the previous video we are checking both ways. 97 00:05:08,730 --> 00:05:09,000 Right. 98 00:05:09,000 --> 00:05:13,530 So the mapping from char s should be to char t in S hash. 99 00:05:13,530 --> 00:05:17,490 And the mapping should be from char t to char s in t hash. 100 00:05:17,490 --> 00:05:21,450 If either of these mappings is not true, then we return false. 101 00:05:21,450 --> 00:05:26,160 And if we are not able to return false and we come out of the for loop, then we return true. 102 00:05:26,160 --> 00:05:27,570 So that is our function. 103 00:05:27,570 --> 00:05:30,510 Now let's quickly run it and test our function. 104 00:05:30,510 --> 00:05:32,220 So I have checked isomorphic. 105 00:05:32,220 --> 00:05:34,020 So let's just call this function. 106 00:05:34,470 --> 00:05:38,460 And let's just pass a and b. 107 00:05:38,730 --> 00:05:39,120 All right. 108 00:05:39,120 --> 00:05:41,970 So the expectation is that it should be true right. 109 00:05:41,970 --> 00:05:43,350 So A is mapping to B. 110 00:05:43,350 --> 00:05:44,400 So it should be true. 111 00:05:44,400 --> 00:05:45,570 Yes we are getting true. 112 00:05:45,570 --> 00:05:48,690 Now what if the lengths are not the same now it should be false. 113 00:05:48,690 --> 00:05:49,860 Yes it's false. 114 00:05:49,860 --> 00:05:51,810 What if I put B over here again. 115 00:05:51,810 --> 00:05:52,620 It should be false right. 116 00:05:52,620 --> 00:05:55,980 Because A and c is mapping to B which is not allowed. 117 00:05:55,980 --> 00:05:58,620 What if I change this to D then it's true. 118 00:05:58,620 --> 00:05:58,890 Yes. 119 00:05:58,890 --> 00:05:59,700 That's working. 120 00:05:59,700 --> 00:06:00,180 All right. 121 00:06:00,180 --> 00:06:05,010 Now what about having a over here now having B over here. 122 00:06:05,010 --> 00:06:06,600 In this case it should be true. 123 00:06:06,600 --> 00:06:06,900 Yes. 124 00:06:06,900 --> 00:06:07,860 We are getting true. 125 00:06:07,860 --> 00:06:10,380 Now if this was something else for example. 126 00:06:10,380 --> 00:06:11,490 Ah it should be false. 127 00:06:11,490 --> 00:06:11,910 Yes. 128 00:06:11,910 --> 00:06:13,380 So this is working. 129 00:06:13,380 --> 00:06:14,580 Our function is working. 130 00:06:14,580 --> 00:06:18,780 Now let's quickly walk through the code and let's take a sample. 131 00:06:18,780 --> 00:06:19,890 We have the sample over here. 132 00:06:19,890 --> 00:06:21,150 Let's see what's happening over here. 133 00:06:21,150 --> 00:06:22,500 And let's walk through the code. 134 00:06:24,430 --> 00:06:27,190 So let's quickly see what's happening over here. 135 00:06:27,220 --> 00:06:33,400 Now we have a, a c a and b b d are over here right now. 136 00:06:33,400 --> 00:06:39,640 Once we call the function and we are inside the function, we are going to check whether these two are 137 00:06:39,640 --> 00:06:40,300 of equal length. 138 00:06:40,300 --> 00:06:41,590 So that is done over here. 139 00:06:41,590 --> 00:06:44,170 Now we see that both of them are of length four. 140 00:06:44,170 --> 00:06:45,790 So we don't return over here. 141 00:06:45,790 --> 00:06:47,470 And then we come over here right. 142 00:06:47,470 --> 00:06:49,030 So we have this hash over here. 143 00:06:49,030 --> 00:06:50,740 So let's just write that as hash. 144 00:06:51,590 --> 00:06:53,750 And we have to hash over here. 145 00:06:55,140 --> 00:07:01,410 Now, once we are inside the for loop, we are going to loop from I is equal to zero till I is less 146 00:07:01,410 --> 00:07:02,400 than s dot length. 147 00:07:02,400 --> 00:07:04,110 So in this case this is four. 148 00:07:04,110 --> 00:07:07,980 So I will take the value zero, one, two and three. 149 00:07:08,220 --> 00:07:14,130 Now when I is equal to zero we are going to take the character at the zeroth index over here. 150 00:07:14,130 --> 00:07:16,260 That's a and over here that's B. 151 00:07:16,260 --> 00:07:19,140 And we are going to check is there an entry over here. 152 00:07:19,140 --> 00:07:22,290 So at this point these two are empty right. 153 00:07:22,290 --> 00:07:23,640 So these two are empty. 154 00:07:24,000 --> 00:07:27,450 Now at this point we see that's hash at char s. 155 00:07:27,450 --> 00:07:29,460 That is s hash at a. 156 00:07:29,460 --> 00:07:31,170 There is no key a over here. 157 00:07:31,170 --> 00:07:33,030 So we make this entry over here right. 158 00:07:33,030 --> 00:07:35,130 So we put a over here as the key. 159 00:07:35,130 --> 00:07:37,860 And char t which is b is the value. 160 00:07:37,860 --> 00:07:42,330 Similarly we check whether there is an entry for B over here which is not there. 161 00:07:42,330 --> 00:07:42,570 Right. 162 00:07:42,570 --> 00:07:44,730 So we make an entry of B over here. 163 00:07:44,730 --> 00:07:47,370 And the value is char s which is a. 164 00:07:47,370 --> 00:07:48,000 All right. 165 00:07:48,030 --> 00:07:50,640 Now over here because we made these entries right. 166 00:07:50,640 --> 00:07:53,700 These this condition over here will definitely not be true. 167 00:07:53,700 --> 00:07:53,910 Right. 168 00:07:53,910 --> 00:07:55,170 So we don't return false. 169 00:07:55,170 --> 00:07:59,460 Now s hash at char s is equal to char t which is b. 170 00:07:59,490 --> 00:08:00,990 We just made that entry right. 171 00:08:00,990 --> 00:08:04,770 Similarly t hash at char t which is b is equal to a. 172 00:08:04,800 --> 00:08:06,090 We just made that entry. 173 00:08:06,090 --> 00:08:06,570 All right. 174 00:08:06,570 --> 00:08:08,340 So again I becomes one. 175 00:08:08,340 --> 00:08:08,880 Now. 176 00:08:09,300 --> 00:08:12,150 Now we take the values again a and b. 177 00:08:12,150 --> 00:08:16,740 At this point we see that this these two conditions are not true. 178 00:08:16,740 --> 00:08:17,250 Right. 179 00:08:17,250 --> 00:08:19,740 S hash at s is not undefined. 180 00:08:19,740 --> 00:08:22,020 And t hash at char t is not undefined. 181 00:08:22,020 --> 00:08:23,910 So we don't go inside over here. 182 00:08:23,910 --> 00:08:25,290 And then we come over here. 183 00:08:25,290 --> 00:08:28,140 Now we are going to check whether these are equal right. 184 00:08:28,140 --> 00:08:29,550 So s hash a char s. 185 00:08:29,580 --> 00:08:30,480 This is a. 186 00:08:30,480 --> 00:08:33,480 So is that is it having the value b. 187 00:08:33,480 --> 00:08:36,900 So we don't want if it was not b then we would have returned false. 188 00:08:36,900 --> 00:08:39,900 But at this point yes this is mapping to b. 189 00:08:39,900 --> 00:08:42,630 So and we have a map to B over here. 190 00:08:42,630 --> 00:08:45,060 And then we have B mapped to A over here as well. 191 00:08:45,060 --> 00:08:46,950 So we don't return false. 192 00:08:46,950 --> 00:08:47,340 Right. 193 00:08:47,340 --> 00:08:50,040 So again I is incremented I becomes two. 194 00:08:50,070 --> 00:08:52,950 Now we take this we take C and we take D. 195 00:08:52,950 --> 00:08:53,370 Right. 196 00:08:53,370 --> 00:08:56,250 And over here we see that these entries are not there. 197 00:08:56,250 --> 00:09:01,020 So we make that entry c and d and d and C over here. 198 00:09:01,020 --> 00:09:01,560 Right. 199 00:09:01,560 --> 00:09:05,700 And again because we just made the made the entry this will not be true. 200 00:09:05,700 --> 00:09:08,460 We don't return false I is incremented to three. 201 00:09:08,460 --> 00:09:10,740 Again we get A and we get R right. 202 00:09:10,740 --> 00:09:12,510 We get a and we get R. 203 00:09:12,510 --> 00:09:16,800 So when we come over here we see that the entry is there. 204 00:09:16,800 --> 00:09:17,160 Right. 205 00:09:17,160 --> 00:09:18,630 So we don't do it. 206 00:09:18,750 --> 00:09:19,770 It does not go over here. 207 00:09:19,770 --> 00:09:21,180 It does not go in over here. 208 00:09:21,180 --> 00:09:25,620 And when we come over here for R we see that there is no entry. 209 00:09:25,620 --> 00:09:29,490 So we make an entry over here R which is mapped to a at this point. 210 00:09:29,490 --> 00:09:33,030 Now over here we are going to check s hash at char s. 211 00:09:33,030 --> 00:09:34,830 So that is for a right. 212 00:09:34,830 --> 00:09:36,510 So that is equal to b. 213 00:09:36,510 --> 00:09:39,510 But char t at this point is equal to r. 214 00:09:39,510 --> 00:09:40,440 That is what we got right. 215 00:09:40,440 --> 00:09:41,130 This is r. 216 00:09:41,160 --> 00:09:43,380 Therefore these are not equal. 217 00:09:43,380 --> 00:09:45,030 And we will just return false. 218 00:09:45,030 --> 00:09:46,740 And that's how the function works. 219 00:09:46,740 --> 00:09:49,890 So we see that these two are not isomorphic. 220 00:09:49,890 --> 00:09:56,370 Now if we had instead of R if we had b over there then we would have come out of it right. 221 00:09:56,370 --> 00:09:57,930 So again we don't return false. 222 00:09:57,930 --> 00:10:01,770 And then I will become equal to four which is not less than four. 223 00:10:01,770 --> 00:10:04,950 So we come out of it and we would have returned true over here. 224 00:10:04,950 --> 00:10:05,490 All right. 225 00:10:05,490 --> 00:10:07,320 So we have seen how the function works. 226 00:10:07,320 --> 00:10:10,080 Now what about the space and time complexity. 227 00:10:10,080 --> 00:10:13,560 We can see that the space complexity is O of one. 228 00:10:13,560 --> 00:10:13,740 Right. 229 00:10:13,740 --> 00:10:14,880 So this is a bit tricky. 230 00:10:14,880 --> 00:10:15,480 Why is that. 231 00:10:15,480 --> 00:10:20,940 So we are definitely consuming auxiliary space when we make these two hash tables. 232 00:10:20,940 --> 00:10:21,330 Right. 233 00:10:21,330 --> 00:10:24,300 But still the space complexity is O of one. 234 00:10:24,300 --> 00:10:30,960 Because in the question it's mentioned that the two strings S and T consist of valid Ascii characters. 235 00:10:30,960 --> 00:10:34,290 And the important thing is that that's a fixed size, right. 236 00:10:34,290 --> 00:10:37,560 So there are a fixed number of valid Ascii characters. 237 00:10:37,560 --> 00:10:41,310 So the space complexity is O of some constant. 238 00:10:41,310 --> 00:10:41,730 Right. 239 00:10:41,730 --> 00:10:45,990 So we can we can say that that's something like 256 or so. 240 00:10:45,990 --> 00:10:49,170 But whatever number this is just going to be a constant number. 241 00:10:49,170 --> 00:10:52,500 And O of a constant is nothing but O of one. 242 00:10:52,500 --> 00:10:52,770 Right. 243 00:10:52,770 --> 00:10:56,580 So that's why the space complexity of this solution is O of one. 244 00:10:56,580 --> 00:10:58,050 And the time complexity. 245 00:10:58,050 --> 00:11:02,760 When it comes to the time complexity, we can see that we are just looping once, right? 246 00:11:02,760 --> 00:11:04,170 So we just have one for loop. 247 00:11:04,170 --> 00:11:11,070 So the time complexity is O of n just by using this one for loop we are we are looping through the two 248 00:11:11,070 --> 00:11:11,880 given strings. 249 00:11:11,880 --> 00:11:17,070 We are we are having the values from I zero to s dot length minus one. 250 00:11:17,070 --> 00:11:20,190 So we are just going over the characters once. 251 00:11:20,190 --> 00:11:23,700 So that's why the time complexity of this solution is o of n.