1
00:00:01,040 --> 00:00:01,910
Hi everyone.

2
00:00:01,910 --> 00:00:03,500
Let's do this question.

3
00:00:03,500 --> 00:00:08,420
Given two strings, S and T, determine if they are isomorphic.

4
00:00:08,450 --> 00:00:16,340
Two strings S and T are isomorphic if the characters in S can be replaced to get T, all occurrences

5
00:00:16,340 --> 00:00:21,800
of a character must be replaced with another character while preserving the order of characters.

6
00:00:21,800 --> 00:00:27,830
No two characters may map to the same character, but a character may map to itself.

7
00:00:27,890 --> 00:00:31,490
S and T consist of any valid Ascii character.

8
00:00:31,490 --> 00:00:33,860
All right, now let's take a look at this.

9
00:00:33,860 --> 00:00:36,650
Now we have S over here and we have T over here.

10
00:00:36,650 --> 00:00:40,460
So let's try to understand this question using these two examples.

11
00:00:40,460 --> 00:00:47,720
Now it says that we should get from S to T by replacing every character in S with another particular

12
00:00:47,720 --> 00:00:48,200
character.

13
00:00:48,200 --> 00:00:51,590
So for example over here we replace a with r.

14
00:00:51,620 --> 00:00:55,460
Now you can see that over here also we replace a with R right.

15
00:00:55,460 --> 00:01:02,960
And b is replaced with I, c is replaced with f, u is replaced with g and s is replaced with s.

16
00:01:02,960 --> 00:01:05,120
So this over here is true.

17
00:01:05,120 --> 00:01:10,640
So we can understand that these two strings over here's and T are isomorphic.

18
00:01:10,640 --> 00:01:13,640
Now let's look at a case where they are not isomorphic.

19
00:01:13,640 --> 00:01:16,610
Now over here we can see that we have mapped A to P.

20
00:01:16,610 --> 00:01:19,760
But in this case again A is mapped to R right.

21
00:01:19,760 --> 00:01:21,590
So the mapping is not unique.

22
00:01:21,590 --> 00:01:23,210
Therefore this is false.

23
00:01:23,210 --> 00:01:27,200
So S and R over here these two strings are not isomorphic.

24
00:01:27,200 --> 00:01:31,670
So that is what it means when we say that two strings are isomorphic.

25
00:01:31,670 --> 00:01:32,060
All right.

26
00:01:32,060 --> 00:01:39,410
So a string a character in string S has to map to some other character or itself in T.

27
00:01:39,440 --> 00:01:43,460
Now if we take a to R then you cannot have.

28
00:01:43,460 --> 00:01:44,810
You also map to R.

29
00:01:44,810 --> 00:01:49,640
So that is mentioned also over here no two characters may map to the same character.

30
00:01:49,640 --> 00:01:52,730
So we have understood what is being tested over here.

31
00:01:52,730 --> 00:01:56,900
So we have to write a function and s and t will be given to us.

32
00:01:56,900 --> 00:02:02,780
We have to check whether they are isomorphic or not, and if they are isomorphic we have to return true.

33
00:02:02,780 --> 00:02:05,600
And if they are not isomorphic, we have to return false.

34
00:02:05,600 --> 00:02:06,860
So that's the question.

35
00:02:06,860 --> 00:02:13,040
Now remember in the interview, if you have any questions, ensure that you ask sufficient clarifying

36
00:02:13,040 --> 00:02:18,560
questions so that you are clear that you have understood the question as the interviewer has stated

37
00:02:18,560 --> 00:02:19,130
it to you.

38
00:02:19,130 --> 00:02:22,040
Now let's proceed and write some test cases over here.

39
00:02:22,040 --> 00:02:27,650
Now let's say A is a, b, a, b, r, and t is e o e o o.

40
00:02:27,770 --> 00:02:31,010
Now over here you can see that b is mapped to O.

41
00:02:31,130 --> 00:02:33,350
But r is also mapped to O.

42
00:02:33,350 --> 00:02:36,410
And this is a violation of the condition which we just now discussed.

43
00:02:36,410 --> 00:02:36,710
Right.

44
00:02:36,710 --> 00:02:41,840
So if this these are the two strings given to us then we would have to return false.

45
00:02:41,990 --> 00:02:44,450
Now let's look at another test case.

46
00:02:44,450 --> 00:02:49,130
And again over here it's false because two characters cannot map to the same character.

47
00:02:49,130 --> 00:02:49,370
Right.

48
00:02:49,370 --> 00:02:51,980
And that's what's happening over here B is mapped to O.

49
00:02:51,980 --> 00:02:53,570
And R is also mapped to O.

50
00:02:53,600 --> 00:02:55,580
Now let's look at another test case.

51
00:02:56,030 --> 00:03:02,480
Let's say the strings given to us are a, b, a, b, r and p q r q o.

52
00:03:02,660 --> 00:03:06,890
Now over here we can see that a is mapped to p over here.

53
00:03:06,890 --> 00:03:11,720
But then again A is mapped to R over here which is not allowed right.

54
00:03:11,720 --> 00:03:14,750
It should be unique if A is mapped to P over here.

55
00:03:14,750 --> 00:03:17,630
Over here also A should have mapped to P right.

56
00:03:17,630 --> 00:03:22,970
So again because of this reason, if these are the two strings given to us we would have returned false.

57
00:03:22,970 --> 00:03:26,210
Right now B is mapped to Q which is correct.

58
00:03:26,210 --> 00:03:28,070
And over here also b is mapped to q.

59
00:03:28,070 --> 00:03:29,060
That is correct.

60
00:03:29,060 --> 00:03:30,410
And r is mapped to O.

61
00:03:30,470 --> 00:03:32,390
That is also not an issue over here.

62
00:03:32,390 --> 00:03:35,720
If we had P then we would have identified this as true.

63
00:03:35,720 --> 00:03:36,140
All right.

64
00:03:36,140 --> 00:03:37,370
Now what.

65
00:03:37,370 --> 00:03:38,990
Now let's take another example.

66
00:03:38,990 --> 00:03:43,670
Let's say we have S as green and t as ABCd.

67
00:03:44,060 --> 00:03:46,730
Now over here g is mapped to a all right.

68
00:03:46,730 --> 00:03:50,810
And r is mapped to B, e is mapped to c, E is mapped to c.

69
00:03:50,810 --> 00:03:51,380
That's true.

70
00:03:51,380 --> 00:03:52,490
And n is mapped to D.

71
00:03:52,490 --> 00:03:54,770
So yes over here we have true.

72
00:03:54,800 --> 00:03:59,480
Now what would be the case if we have s as let's say a b, c.

73
00:03:59,660 --> 00:04:04,790
And let's say we have t as p and q right.

74
00:04:04,790 --> 00:04:07,160
So in this case we would have to return false.

75
00:04:07,160 --> 00:04:08,030
Why is that so.

76
00:04:08,030 --> 00:04:09,800
Because C is not mapped to anything.

77
00:04:09,800 --> 00:04:11,960
But C has to be mapped to something right.

78
00:04:11,960 --> 00:04:16,100
It has to either map to C itself or another character.

79
00:04:16,100 --> 00:04:16,340
Right.

80
00:04:16,340 --> 00:04:19,190
So in this case also we would have to return false.

81
00:04:19,190 --> 00:04:23,300
So we have understood the question and we have written out test cases.

82
00:04:23,300 --> 00:04:25,400
So we have a good understanding of the question.

83
00:04:25,400 --> 00:04:30,110
In the next video let's try to think about how we can solve this question.