Freedom Trail - Leetcode 514 - Python

0:00 - Read the problem
0:30 - Drawing Recursive
9:45 - Coding Recursive
15:15 - Drawing DP
20:40 - Coding DP

leetcode 514

#neetcode #leetcode #python

[siddharth-gandhi]

bro single handedly saving my streak. thanks for doing this :)

[anand_dudi]

Only channel on whole youtube which is best not just solving leetcode problems but also to explaining the problem as much as simple possible with many approaches DAMM

[yang]

These problem descriptions are getting out of hand

[huyennguyenmaingoc]

Thank you Neetcode, I learned Algorithm from your series by watching the whole Medium playlist. Now I passed my Codility test and got the first internship, which I thought I couldn't 2 months ago XD

[chaitanya]

another problem with dp vs greedy ... where greedy fails

[williamdufault]

python 80ms - recursion + memoization + binary search

class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
@cache
def dfs(r: int, k: int) -> int:
if k == len(key): return 0

steps = math.inf
for i in get_closest_indexes(r, key[k]):
steps = min(steps, get_min_distance(r, i) + dfs(i, k + 1))

return 1 + steps

def get_closest_indexes(i: int, char: str) -> Tuple[int]:
if ring[i] == char: return (i, )

char_indexes = indexes[char]
if len(char_indexes) == 1: return tuple(char_indexes)

l, r = 0, len(char_indexes) - 1
while l < r:
m = l + (r - l) // 2
if char_indexes[m] < i:
l = m + 1
else:
r = m - 1

return (
char_indexes[l],
char_indexes[l - 1] if char_indexes[l] > i \
else char_indexes[(l + 1) % len(char_indexes)]
)

def get_min_distance(i: int, j: int) -> int:
diff = abs(i - j)
return min(diff, len(ring) - diff)

indexes = defaultdict(list)
for i, char in enumerate(ring):
indexes[char].append(i)

return dfs(0, 0)

[SaiPreethamDasari]

For the recursive solution with memoization, although it makes the code a little messier, you don't really need to consider all possible occurrences of a particular key character in the ring. Finding the first occurrence of the required character towards the left and the right and then recursively solving the rest of the problem is also adequate! But yeah great solution that helped me save my streak! Keep writing more neet code! :D

[yassine-sa]

I just saw now that this is the same problem we'll have to solve if we tried to type a string using a wheel that contains letters if we have the same mechanism as the those old phone wheels, the only difference is that phone wheels has has only numbers and they appear only once, this is a more general situation

[yassine-sa]

Am I supposed to have a solution that works from the first try "normally"? because I always write a solution that works for basic cases and then I start finding bugs I didn't see after submitting the thing, I think that's because I don't completely see what my code is doing until I get a hint by the failed submissions that probably this part isn't working, how do you guys deal with this? is it just me or it's about me not trying to go over the code again and again to try and catch bugs before submitting the solution, if that's the case, is it really what should happens when coding in real life situations?

[raghavrathi]

Please do yesterday's daily question i.e sum of distances in a tree, it seems like a really good question

[IK-xkex]

I recognise that it is DP problem, but I get stuck at the moment how to find circular offset, blain on me. After the moment you get the explanation I solved it by myself.

[Munchen]

Neetcode, thank you for detailed explanation specially when using recursion. A decision tree really helps to divide and conquer the problem. By the way dp solution are better. Thanks 😊

[tanzeembelal]

Please solve contest problems for leetcode it will be so beneficial your quality of explanation is what we want please please please

[hida-steak-donburi]

Whoelse came up with Greedy solution and got suboptimal like me...

[sheersendughosh]

Thanks for the solution! If we come up with the caching solution and not the best optimal approach is it considered bad in an real interview? Can you kindly show/share code snippet for both caching solution and the optimal sol that you would do in a real FAANG interview? Love your videos❤

[diasutsman]

Bro the video embed in your courses are not working

[MP-nyep]

Phenomenal explanation as always. Thank you

[get_out_it]

I’m adept at problem solving complex technical issues)

[wytsai]

4:55 Sorry, but I still can’t see why trying every characters (those three 'b's) won’t make our solution more inefficient 😢 Can somebody explain to me 🙏

[shahnawazhussain]

Hii. I have a request. Please make a video on the problem "1915: Number of wonderful substrings". No matter how hard i try i could not understand the logic. I watch your videos and i think you can explain it to me. And i am pretty sure i will understand if you make a video on this problem. Please take it as a request. Thanks. love your videos <3