1 00:00:00,170 --> 00:00:05,360 Let's now get into the code and write the recursive approach that we have discussed in the previous 2 00:00:05,360 --> 00:00:05,930 video. 3 00:00:05,930 --> 00:00:09,950 So we again given S which is the string, and we given our dictionary. 4 00:00:09,950 --> 00:00:10,430 Okay. 5 00:00:10,430 --> 00:00:14,810 Now let's say n is the length of the given string. 6 00:00:15,950 --> 00:00:19,070 And we will need a helper function. 7 00:00:19,070 --> 00:00:21,620 Let's just call it check ending hat. 8 00:00:21,620 --> 00:00:22,160 Okay. 9 00:00:23,360 --> 00:00:26,480 And to this function we'll have to pass an index. 10 00:00:26,780 --> 00:00:29,450 Now again what is this function going to return. 11 00:00:29,480 --> 00:00:32,870 This function will either return true or false. 12 00:00:32,870 --> 00:00:37,940 And it's basically checking up to this particular index over here from zero. 13 00:00:37,940 --> 00:00:43,010 Whether that particular substring can be formed with words from word dictionary. 14 00:00:43,040 --> 00:00:43,520 Okay. 15 00:00:43,520 --> 00:00:49,520 And when we call this function for the first time, we will have to pass the last valid index which 16 00:00:49,520 --> 00:00:51,800 is n minus one because n is the length of the string. 17 00:00:51,800 --> 00:00:52,160 Okay. 18 00:00:52,160 --> 00:00:58,040 So this actually would check whether the complete string that is from index zero up to index n minus 19 00:00:58,040 --> 00:01:01,340 one can be formed using words from word dictionary. 20 00:01:01,340 --> 00:01:06,620 And because this will either return true or false, we can just return what we get back from this. 21 00:01:06,620 --> 00:01:10,340 So this is the skeleton of the approach that we are going to implement over here. 22 00:01:10,340 --> 00:01:12,530 Now let's go ahead and write the details. 23 00:01:12,530 --> 00:01:19,370 So over here we'll be writing the base case as well as the recursive case okay. 24 00:01:19,370 --> 00:01:26,480 And the base case would be the case where the index is less than zero which is the first invalid index. 25 00:01:26,480 --> 00:01:30,920 So if index less than zero then we can just return true. 26 00:01:30,950 --> 00:01:32,780 Now why do we return true. 27 00:01:32,810 --> 00:01:36,590 We have discussed this in the previous video, but let me quickly review this. 28 00:01:36,590 --> 00:01:39,650 Now let's say word dictionary has just one word. 29 00:01:39,650 --> 00:01:44,210 Let's say it's good and let's say s is also good okay. 30 00:01:44,210 --> 00:01:47,000 And let's say we are passing this index over here which is three. 31 00:01:47,090 --> 00:01:53,360 Now once we see a match between what we have in our dictionary and what the string which is given to 32 00:01:53,360 --> 00:01:57,680 us, and again, we're just considering the substring from zero up to this particular index. 33 00:01:57,680 --> 00:02:00,590 And again in this example we see these two match. 34 00:02:00,590 --> 00:02:06,680 So from here we will be moving back four units which is the length of this particular word okay. 35 00:02:06,680 --> 00:02:08,150 And we would reach over here. 36 00:02:08,150 --> 00:02:10,580 And this is actually less than zero okay. 37 00:02:10,580 --> 00:02:11,930 And that's why we return. 38 00:02:11,930 --> 00:02:12,260 True. 39 00:02:12,260 --> 00:02:14,210 And this is the only way that this would happen. 40 00:02:14,210 --> 00:02:17,990 Because in the question again it's mentioned we will not be given an empty string. 41 00:02:17,990 --> 00:02:22,910 And for a scenario to happen where index is less than zero, this would be the case okay. 42 00:02:22,910 --> 00:02:25,700 And again that's why we can return true in this case. 43 00:02:25,700 --> 00:02:28,370 Now let's proceed to the recursive case. 44 00:02:28,550 --> 00:02:33,230 And for this we would have to iterate through every word in the word dictionary. 45 00:02:33,230 --> 00:02:37,490 So I can say for let word of word dictionary okay. 46 00:02:37,490 --> 00:02:41,210 And we have index over here which is the ending index. 47 00:02:41,210 --> 00:02:46,310 And because we are considering this particular word we'll have to calculate the start index. 48 00:02:46,310 --> 00:02:53,510 And start index is going to equal the end index minus the word length plus one okay. 49 00:02:53,510 --> 00:02:55,460 So that gives us the start index. 50 00:02:55,460 --> 00:03:05,240 And now we will just check whether s dot substring from start to index okay. 51 00:03:05,240 --> 00:03:10,850 So we'll just check whether this particular substring is equal to the word that we are considering. 52 00:03:10,850 --> 00:03:16,610 And if this is true then we will also check whether the previous part of this particular substring can 53 00:03:16,610 --> 00:03:18,890 be formed using words from word dictionary. 54 00:03:18,890 --> 00:03:23,360 And for that we will be just calling the check ending at function recursively. 55 00:03:23,360 --> 00:03:29,000 And to this we will pass the index as start minus one, which again is the ending index. 56 00:03:29,000 --> 00:03:29,450 Okay. 57 00:03:29,450 --> 00:03:38,540 Now if these two conditions are true then we will just return true, which means that we can form the 58 00:03:38,540 --> 00:03:40,580 substring that goes from zero up to. 59 00:03:40,580 --> 00:03:44,300 This particular index can be formed using words from our dictionary. 60 00:03:44,300 --> 00:03:50,570 And if we are not able to return true over here, and once we come out of the for loop, we will just 61 00:03:50,570 --> 00:03:51,710 return false. 62 00:03:52,490 --> 00:03:56,630 Okay, so this is the recursive solution to the word break problem. 63 00:03:56,630 --> 00:04:01,040 Now let's go ahead and run this code and see if it's passing all the test cases. 64 00:04:02,890 --> 00:04:04,660 And you can see that it's working. 65 00:04:04,660 --> 00:04:06,280 It's passing all the test cases. 66 00:04:06,280 --> 00:04:12,070 Now in the next video, let's go ahead and memorize this to achieve a much better time complexity.