Strings & Palindromes | Recursion Series

Key Takeaways

foreign [Music] welcome back I'm William and this is a continuation of the recursion Series today I want to begin looking at some string manipulation problems since recursion isn't all about just numbers we use strings all the time in programming and it's essential that we also know how to manage them when using recursion I want to start off by looking at a very simple problem you probably already know how to solve reversing a string so that it reads backwards for example the string three two one would read as one two three and ABC as CBA if you were to implement this problem iteratively the code would probably look something like this you would start by initializing an empty string and then iterate through the characters of the original string backwards adding each character to the new string as you go along and return the result however if you wanted to achieve the same thing recursively how would we go about it well here's one way we could do it our approach would involve using the same strategy of building the string backwards except that we would reverse the string character by character in the return statement notice that on the last line we add the character to the current string position after the recursive call to reverse the string what happens if we invert to the return statement so that the current character is before the recursive call to the reverse function I'll give you a moment to think about that the answer is that that would make a copy of the string instead of reversing the string since we would be constructing the string in order instead of in reverse order we just looked at probably the simplest way to reverse a string however there's another method we can use to reverse a string by reversing it outside in rather than linearly let's take the string Dragon for instance if we take the front and the back characters of the string then we can swap them once you have swapped the outer parts of the string the only remaining portion that has not yet been reversed is the intersection highlighted in blue we can then recursively apply to the same process to that intersection of the string we pick out the first and last characters swap their positions identify the remaining portion of the string that hasn't yet been reversed and recursively apply the same process eventually there are no more characters to swap so the recursion would unwind and we would construct the Reversed string and that's another way to reverse a string using the outside in method this is the pseudocode for the outside in method let's take a short walk through it in the base case we verify if the String's length is less than or equal to one in which case we would return the current string this base case handles the scenarios where the remaining string has a length of zero or one if the remaining string is empty which occurs in even length strings we return an empty string however if there is one character left after reducing the string using the outside inner approach we return that character since it represents the middle character of the string and the middle character is the reverse of itself so if we're not in a base case situation we want to swap the lactomose and the rightmost characters of the string the highlighted line gets the left and the right characters from the string s in the following line we extract a substring of the inner string so that we can pass it down to the reverse function we specify that the substring should start at index one and end at index n minus 1 to exclude the first and the last characters if you were to visualize the variable assignments from the pseudo code left corresponds to the leftmost character substring to the inner blue segment and right to the rightmost character of the string afterwards we would recursively call the reverse function swapping the left and the right characters and the return statement as we build the string and that's pretty much how we would reverse the string using the outside in method however just one question for you guys what happens if we update the code to check if the length of the string is zero instead of less than or equal to one will this still reverse the string as intended I'll give you a moment to think about it the answer is that the reverse function will continue to work for even length strings but will fail to produce the right answer for odd length strings what happens is that the middle character would get duplicated if we don't handle the N equals one case since both the left and the right variables would point to the same character all right we just finished looking at how to reverse a string recursively now let's shift our attention to something slightly different but related which is the problem of identifying whether a string is a palindrome or not palindromic strings are strings which read the same backwards and forwards meaning you can reverse the string and you get the original string you started with for example the word Rotator is read the same whether you read it forwards or backwards however a string like raccoon is not a palindrome since reading the string backwards doesn't match the original string and one more example the string of numbers one two three four three two one is a palindrome because it reads the same backwards and forwards if you've been paying attention you may have noticed that we can easily create a function to check if a string is a palindrome or Not by reusing the previously implemented reverse function simply check whether the string is equal to the reverse of itself now I have a challenge for you guys to implement the ispondrome function but by using the outside method we discussed previously to check if the string is a palindrome So Below I have the is palindrome method with some simple examples of whether or not the following strings should be considered a palindrome or not I'm going to reveal the solution in the next slide so be sure to stop the video and give this challenge a try I'm going to give you a short moment all right I hope you guys took the time to try out that mini challenge the way we're going to verify if the string is a pound drum or not is by working outside in we're going to check if the first and the last characters of the string match and recursively apply this technique to the inner substring if at any point the first and the last characters don't match we can stop the recursion and return false to indicate that the string is not a palindrome first we check if the outermost characters match after verifying that they do recursively check if the inner string is also a palindrome check that the first and the last characters match then repeat the same process once we reach the end we know that this string is indeed a palindrome and can return true here's some pseudocodone how you would check that the string is a pound drone using the outside in method we just looked at first we check our base case to see if the length of the string is less than or equal to one this indicates that the recursion has come to an end and that the string is now either a single character or an empty string both of which are trivially palindromes then we check if the first and the last characters match if they do then recursively call the ispoundra method to check it if the inner substring not including the first and the last characters is also a palindrome otherwise if the first and the last characters do not match immediately return false and end the recursion awesome that's all I have for you guys on strings and palindromes for now thank you for watching please like this video And subscribe if you learned something and I'll catch you in the next one