Strings & Palindromes | Recursion Series
Вставка
- Опубліковано 15 лип 2024
- In this video we explore how to reverse a string using recursion and check whether or not a string is a palindrome using the 'outside-in' method.
Source code repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/algor...
Woahhhh you are back . Hey William ....huge fan of your content . Welcome back ❤
Welcome back . Need graph series
Graph Theory Playlist: ua-cam.com/play/PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P.html
Your video on recursion has really deepened my understanding of recursion to great detail….👍🏾👍🏾👍🏾
Welcome back
🔥🔥
Can you do recurtion for permutation?
def different_chars(string1, string2):
if len(string1) != len(string2):
raise Exception("Strings must be of equal length")
chars = set() # could be returned as empty
for i in range(len(string1)):
if string1[i] != string2[i]:
chars.add(string2[i])
return chars
print(different_chars("racecar", "racecar"))
print(different_chars("hey", "bye"))
thanks
Lit ❤
def reverse_string(string):
if len(string) == 0:
return string
return reverse_string(string[1:]) + string[0]
def is_palindrome(string):
backwards = reverse_string(string)
if backwards == string:
return True
return False
print(f"Palindrome: {is_palindrome("racecar")}")
@4:25 , I think it should be substring = s.substring ( 1 , n - 2 ); not n-1
n-2 I think might truncate the string too much. Using n-1 reduces the length of the string by one character each time.
@@WilliamFiset-videos left = s[0] , right = s[n-1] , then the substring that we will pass, must exclude the first(0) and last(n-1) to be s.substring(1,n-2) , the new string ,, idk but i didn't work with me when n-1 but thanks for reply & the great video
Both substring and concatenation are O(N), thus the whole reverse is O(N^2). Not sure about length, but it might be implemented outside of interpreter, and thus incur context switching costs. Worse, Python doesn't even do tail-call optimization, so recursion is almost guaranteed to shoot you in the feet. I don't know what the point of such implementation of reverse was, but it didn't go well.
All good points about optimization. I agree that in practice you wouldn't implement a string reversal function recursively. The goal of the video is to get a better understanding of how recursion works.
I think the point of this video is to understand how recursion works, how the recursive calls stacks up before hitting the base case and how the results of the stacks are accumulated and returned after the base case is satisfied in the unwinding phase. That is the biggest lesson I have learnt in this video.