1
00:00:01,050 --> 00:00:02,020
Hello, everyone.

2
00:00:02,040 --> 00:00:07,430
So in this video, we are going to discuss one more question, so let me explain you what is the question?

3
00:00:07,680 --> 00:00:09,450
So you are provided with the map.

4
00:00:11,290 --> 00:00:16,820
So you are provided with a map and this is the key and this is the corresponding value.

5
00:00:16,990 --> 00:00:19,390
Similarly, this is the key and this is the value.

6
00:00:19,570 --> 00:00:21,680
So this is the key and this is the value.

7
00:00:21,820 --> 00:00:23,700
So you have a map of type.

8
00:00:24,130 --> 00:00:26,370
Key is string key.

9
00:00:26,380 --> 00:00:28,510
We have a string and it is a value.

10
00:00:28,750 --> 00:00:32,710
Value is basically a list or we can see a vector already.

11
00:00:32,920 --> 00:00:36,880
So value is basically a list of veterinary and list of string.

12
00:00:36,880 --> 00:00:40,210
So each word is basically a string.

13
00:00:42,020 --> 00:00:49,640
So we are given this map and we are given a paragraph, so we are given a paragraph, for example,

14
00:00:49,640 --> 00:00:56,240
lion girls, leopard, dot, dot, dot, dot, dot, dot, dot, dot, dot, dot, dot, dot, dot,

15
00:00:56,240 --> 00:00:57,890
beautiful, battered, dot, dot, dot.

16
00:00:57,890 --> 00:01:00,420
And so this is a very long paragraph.

17
00:01:00,440 --> 00:01:07,770
OK, and now what we need to do so we need to replace the words which are auguring in paragraph by dakis.

18
00:01:08,450 --> 00:01:10,130
So what do we mean by this.

19
00:01:10,410 --> 00:01:12,980
So for example, lion kills leopard lion.

20
00:01:13,190 --> 00:01:15,800
So Lion is present here and what is its key.

21
00:01:16,130 --> 00:01:17,390
But is the key for lion.

22
00:01:17,400 --> 00:01:19,360
The key for lion is basically cat.

23
00:01:19,610 --> 00:01:24,500
So you need to replace Lion Bichard similarly leopard.

24
00:01:25,010 --> 00:01:27,980
So for leopard what is the key cat.

25
00:01:28,140 --> 00:01:32,380
So you will replace leopard by cat and so on.

26
00:01:32,390 --> 00:01:35,570
So Forwell what is the key is Océane.

27
00:01:35,570 --> 00:01:39,330
So you will replace Will by ocean and so on.

28
00:01:39,350 --> 00:01:41,020
So bad is not present anywhere.

29
00:01:41,030 --> 00:01:44,620
So we will not replace Sharky's present.

30
00:01:44,630 --> 00:01:45,530
So foreshock.

31
00:01:45,530 --> 00:01:47,300
We need to replace it with Océane.

32
00:01:49,850 --> 00:01:55,690
And so on, then beautiful then Pettit's better Betteridge we need to replace it by boards so replace

33
00:01:55,700 --> 00:01:58,720
battered by bird and we keep doing this.

34
00:02:00,410 --> 00:02:02,720
So this is your problem statement.

35
00:02:02,720 --> 00:02:07,780
You need to replace all the words in the paragraph by their corresponding keys.

36
00:02:08,750 --> 00:02:11,430
And now the question is how you can do this.

37
00:02:12,350 --> 00:02:18,770
So what I suggest is you can post a video for five to 10 minutes and then think, and then try to think

38
00:02:18,770 --> 00:02:19,430
of a solution.

39
00:02:20,330 --> 00:02:29,480
So I hope you have both the video and think of a solution and and have given your full attention to

40
00:02:29,480 --> 00:02:30,050
this problem.

41
00:02:30,350 --> 00:02:33,170
So now let's discuss what can be the possible solution.

42
00:02:34,250 --> 00:02:40,190
So first of all, what I'm trying to think it is so this is very difficult, right.

43
00:02:40,850 --> 00:02:46,640
For example, you are given an outline, so how you will be able to find out the key for laying the

44
00:02:46,640 --> 00:02:48,410
Keys card, what to do.

45
00:02:48,590 --> 00:02:54,560
You need to arbitrate over this map and for each key, what you will do, you will iterate over this

46
00:02:55,310 --> 00:02:56,200
basically list.

47
00:02:56,570 --> 00:03:03,410
So forget you will trade over the list and we will compare line with the given word line and then you

48
00:03:03,410 --> 00:03:05,180
will replace the word by card.

49
00:03:05,630 --> 00:03:07,730
So this is a very, very lengthy process.

50
00:03:08,000 --> 00:03:12,830
For example, foreshock or let's take the example of Petitt so far better.

51
00:03:13,010 --> 00:03:13,760
What do you need to do?

52
00:03:14,300 --> 00:03:17,660
You will migrate over this map for each key.

53
00:03:17,690 --> 00:03:20,080
You will migrate over this list.

54
00:03:20,420 --> 00:03:22,100
You will not be able to find Pettit's.

55
00:03:22,430 --> 00:03:25,010
Then for the second key, you will Étretat with this list.

56
00:03:25,010 --> 00:03:27,050
You will not be able to find Pettit's then.

57
00:03:27,050 --> 00:03:32,570
Similarly, for the third, you will be able you will be searching this area, this list, and you will

58
00:03:32,570 --> 00:03:35,680
be able to find Barret's and then you replace by board.

59
00:03:36,530 --> 00:03:42,260
So I think this is a very, very, very lengthy process because we need to do this process for each

60
00:03:42,260 --> 00:03:42,960
and every word.

61
00:03:43,310 --> 00:03:46,250
So for the words, for example, beautiful, what will happen?

62
00:03:46,610 --> 00:03:47,510
You will search here.

63
00:03:47,510 --> 00:03:48,710
You will not find the word.

64
00:03:48,710 --> 00:03:49,360
You will search here.

65
00:03:49,370 --> 00:03:50,900
You will not find the word will search.

66
00:03:50,960 --> 00:03:51,950
You will not find the word.

67
00:03:52,130 --> 00:03:53,930
And it will basically keep searching.

68
00:03:53,930 --> 00:03:59,720
And you will not be able to find the word beautiful and you will not replace since you are not able

69
00:03:59,720 --> 00:04:01,730
to find the word beautiful, you will not replace it.

70
00:04:01,940 --> 00:04:04,150
So it's a very, very, very, very lengthy process.

71
00:04:04,460 --> 00:04:09,950
So one optimization that I can think right now is basically let's try to create a reverse map.

72
00:04:12,320 --> 00:04:14,510
Let's try to create a reverse map of it.

73
00:04:14,630 --> 00:04:16,420
So what do I mean by reverse map?

74
00:04:16,700 --> 00:04:19,310
So I was told like this for line.

75
00:04:19,670 --> 00:04:22,550
I have cared similarly for Tiger.

76
00:04:23,940 --> 00:04:26,820
I have cared similarly for Leopard.

77
00:04:29,290 --> 00:04:33,160
I have cared similarly for shock.

78
00:04:35,670 --> 00:04:37,770
Get ants on some of the first battle.

79
00:04:40,060 --> 00:04:41,140
I have this bird.

80
00:04:43,790 --> 00:04:50,770
So I will prepare one map, I will prepare one map, and this map is of type string on my string keys,

81
00:04:50,780 --> 00:04:54,710
a string, so key is a string and value is also a string.

82
00:04:54,980 --> 00:04:56,570
So value is also a string.

83
00:04:57,830 --> 00:04:59,630
Now, this will improve our searching.

84
00:05:00,500 --> 00:05:01,010
How?

85
00:05:01,010 --> 00:05:07,340
Because for line, if you want to search and nobody will do, you will simply search for the key, you

86
00:05:07,340 --> 00:05:08,630
will simply search for the key.

87
00:05:08,960 --> 00:05:13,580
And that this line you do not etrade, you will simply search for the key line and you will replace

88
00:05:14,060 --> 00:05:15,980
the line by its corresponding value.

89
00:05:16,370 --> 00:05:21,410
Similarly for kids, you just need to call the function search of map.

90
00:05:22,100 --> 00:05:27,350
I think that search function or I think or dart find our dot count function.

91
00:05:27,530 --> 00:05:32,390
So map map provides you the availability to search bickie.

92
00:05:33,890 --> 00:05:34,420
Right.

93
00:05:34,430 --> 00:05:40,040
So for apart will do, you will call the search function off map and it will return you the card.

94
00:05:40,970 --> 00:05:41,380
Right.

95
00:05:41,570 --> 00:05:44,980
So in this way we are improving our searching.

96
00:05:45,080 --> 00:05:51,020
It is lot better than the previous searching because in this case we just need to figure out the world

97
00:05:51,230 --> 00:05:52,490
and how we can figure out the word.

98
00:05:52,520 --> 00:05:58,700
So there are spaces between them to just figure out the word, search this word in this map if the word

99
00:05:58,700 --> 00:06:00,900
is present, replaced by the corresponding value.

100
00:06:01,710 --> 00:06:03,230
Yeah, this solution will work.

101
00:06:04,880 --> 00:06:07,010
This solution is going to work.

102
00:06:08,540 --> 00:06:13,540
But there are problems with the solution and what is the problem.

103
00:06:14,360 --> 00:06:20,690
So problem is, basically, you can see so in map, how many entries are there in this map, in the

104
00:06:20,690 --> 00:06:22,520
input map, how many entries are there?

105
00:06:22,880 --> 00:06:24,440
There are only three entries.

106
00:06:25,560 --> 00:06:32,430
We have only three entries for this map, for the input map, and how many entries do we have in this

107
00:06:32,430 --> 00:06:33,220
reverse map?

108
00:06:33,780 --> 00:06:37,510
So one, two, three, four, five, six, seven and eight.

109
00:06:37,770 --> 00:06:41,480
So we are going to have eight entries in the reverse map.

110
00:06:43,380 --> 00:06:52,350
Now, let's see if this list, if this list is basically of the order 10 to the power six, this list.

111
00:06:52,560 --> 00:06:57,470
Similarly, this list is like containing 10 to the power six items similar.

112
00:06:57,490 --> 00:06:59,850
This list is continuing to deliver six items.

113
00:07:00,060 --> 00:07:02,700
So what you are doing, what will be your size?

114
00:07:03,240 --> 00:07:06,270
So you still have three entries in the map.

115
00:07:07,110 --> 00:07:10,980
But if you will reverse the map, how many entries you are going to have?

116
00:07:11,640 --> 00:07:16,100
10 to the power, six plus 10 to the power, six plus 10 to the power six.

117
00:07:16,800 --> 00:07:19,500
So your map will become huge.

118
00:07:20,840 --> 00:07:21,890
It will become huge.

119
00:07:21,900 --> 00:07:27,420
It is going to take a lot of lot of memory, a lot of lot of memory.

120
00:07:27,420 --> 00:07:35,970
And although we improved our searching but for improving the searching, we are taking a lot of memory

121
00:07:36,570 --> 00:07:38,070
and we don't want that.

122
00:07:39,270 --> 00:07:45,860
So this is the first limitation of this solution that your memory consumption will be huge.

123
00:07:47,430 --> 00:07:51,820
There is one more problem with this approach and what's the problem?

124
00:07:52,200 --> 00:08:00,740
So currently I am saying that the world is lying, but I never said that it will contain only one word.

125
00:08:00,840 --> 00:08:02,390
It can be a list of words.

126
00:08:02,940 --> 00:08:14,130
For example, I have gathered and forget I have like lions and cubs, lions and their children.

127
00:08:14,640 --> 00:08:22,950
Similarly, I can have like tigers and tigers or female tiger.

128
00:08:23,610 --> 00:08:24,030
Right.

129
00:08:24,220 --> 00:08:25,380
So I can have.

130
00:08:25,680 --> 00:08:28,840
So currently you have seen only one word.

131
00:08:29,310 --> 00:08:31,560
What if we have a collection of words?

132
00:08:32,840 --> 00:08:39,320
So if you have a collection of words and if you make a reverse map also so, for example, if you make

133
00:08:39,320 --> 00:08:44,360
the reverse map, that is lying and cubs to get.

134
00:08:46,280 --> 00:08:56,450
So in this paragraph, if the word is lions and cubs, then how you'll be able to figure out when to

135
00:08:56,450 --> 00:08:57,800
stop, right?

136
00:08:57,800 --> 00:08:59,050
There is space between this.

137
00:08:59,060 --> 00:09:04,610
There is space between this and there will be space and also so how you will be able to figure out when

138
00:09:04,610 --> 00:09:05,210
to stop.

139
00:09:07,560 --> 00:09:16,710
So what he will do, what you will do, you will stop headlines, then you will consider lines and then

140
00:09:16,710 --> 00:09:25,950
you will consider lions and cubs, then you will consider lions and cubs and something else.

141
00:09:26,310 --> 00:09:26,700
Right.

142
00:09:26,730 --> 00:09:27,630
There can be something else.

143
00:09:27,720 --> 00:09:36,360
So, for example, lion cubs and we have one more entry in this, which is lions and cubs and something

144
00:09:36,360 --> 00:09:36,670
else.

145
00:09:37,140 --> 00:09:40,530
So basically, you will not be able to figure out when to stop.

146
00:09:41,470 --> 00:09:45,880
So you will take a collection of one word in the paragraph, you will take a collection of one word,

147
00:09:46,420 --> 00:09:50,530
then you will take a collection of two words, then it will take a collection of three words.

148
00:09:50,740 --> 00:09:54,070
Then you will take a collection of four words and keep going on.

149
00:09:54,490 --> 00:09:56,900
You will not be able to figure out when to stop.

150
00:09:57,610 --> 00:10:01,270
So this solution that we have discussed has two major problems.

151
00:10:01,690 --> 00:10:04,240
That memory conception is a lot more.

152
00:10:04,240 --> 00:10:10,510
And this solution will only work when you have only one word and not collection of word.

153
00:10:11,260 --> 00:10:14,580
So here in the input, we are having only one word lion.

154
00:10:14,590 --> 00:10:16,110
We have only one word tiger.

155
00:10:16,300 --> 00:10:18,160
We do not have a collection of words.

156
00:10:19,370 --> 00:10:23,230
OK, so these two are the limitation for the solution that we have discussed.

157
00:10:23,230 --> 00:10:24,610
That is reverse mapping.

158
00:10:25,540 --> 00:10:31,660
Your memory consumption will increase and also this reverse mapping solution will only work if you have

159
00:10:31,660 --> 00:10:34,990
a single word and not a collection of words like this.

160
00:10:35,380 --> 00:10:41,020
If you have the collection of words, you will not be able to figure out when to stop in the paragraph

161
00:10:41,020 --> 00:10:45,200
while you trying to replace the word, you will not be able to figure out when to stop.

162
00:10:45,730 --> 00:10:51,500
So these two are the limitation for this problem, for this solution, basically.

163
00:10:52,180 --> 00:11:01,160
Now, in the next video, what we will do all basically what you should try, can we improve the solution?

164
00:11:02,950 --> 00:11:04,270
So let me give you a hint.

165
00:11:04,870 --> 00:11:10,210
We can definitely improve the solution and how we can improve the solution basically from the last few

166
00:11:10,210 --> 00:11:17,410
lessons we are learning, particularly the structure, which is called Try So and I am discussing this

167
00:11:17,410 --> 00:11:21,190
problem, then it's very obvious that private sector can be used here.

168
00:11:21,670 --> 00:11:27,330
And now the challenge is basically how you will be using private sector for this problem.

169
00:11:28,210 --> 00:11:34,000
So try structure will basically solve both of these problems, the memory problem and also the single

170
00:11:34,000 --> 00:11:34,630
word problem.

171
00:11:35,530 --> 00:11:43,600
So this video is getting Landi, so I will discuss the solution, the next video and you can also think

172
00:11:43,600 --> 00:11:45,440
yourself how that can help us.

173
00:11:45,910 --> 00:11:49,820
So this is pretty much that I want to discuss in this video.

174
00:11:50,260 --> 00:11:52,410
So this is it, guys.

175
00:11:52,420 --> 00:11:53,930
I will see you in the next one.

176
00:11:53,950 --> 00:11:54,520
Thank you.

