String Diff in Python

Chapters:
- 00:00:00 - 1. Intro
- 00:01:44 - 1.1. Levenshtein Distance
- 00:05:02 - 2. Recursive Algorithm
- 00:07:27 - 2.1. Base Cases
- 00:11:20 - 2.2. Recursive Cases
- 00:19:49 - 2.3. Bug
- 00:23:06 - 2.4. Performance problem
- 00:23:57 - 3. Python Memoization
- 00:27:35 - 4. Custom Cache Memoization
- 00:28:21 - 4.1. Passing the lengths of the strings along with the strings
- 00:35:17 - 4.2. 2D Table Cache
- 00:36:07 - 4.3. Constructing 2D Table in Python
- 00:38:41 - 4.4. Extra row and column in the table
- 00:40:17 - 4.5. Integrating the table with the algorithm
- 00:43:34 - 5. Recovering the Reference Implementation
- 00:46:17 - 6. How the cache changes over time?
- 00:46:50 - 6.1. Python Pretty-Print
- 00:49:00 - 6.2. Custom Pretty-Print
- 00:52:21 - 6.3. Cache is not visited fully
- 00:55:34 - 7. Non-Recursive Algorithm
- 01:09:02 - 8. Dynamic Programming
- 01:14:14 - 9. Computing the Sequence of Actions
- 01:15:26 - 9.1. Table of Actions
- 01:27:10 - 9.2. Back tracing
- 01:32:39 - 9.3. Implementation
- 01:36:43 - 9.4. Making sense of the back trace
- 01:47:24 - 9.5. Reporting specific characters in the back trace
- 01:53:31 - 10. QnA
- 01:55:09 - 11. Outro
- 01:55:21 - 12. Smooch

References:

[trentmhuber]

Waiting for the day where he pings everyone that DOESN'T want to be pinged

[irqtsk]

Perfect timing for this video. My algorithms class is covering this algorithm, but you explain it so much better. Thank you.

[sent]

I checked and it totally works for strings instead of characters. Building upon this, you can also make some sort of fuzzy string equality (using the same old levenshtein distance) and replace substitution operation with editing operation for file diffs

[soupnoodles]

awesome, python content is something I'd watch

[ZephyrCubic]

For the last problem you were having with the extra ignore, the “while n1 >= 0 and n2 >= 0” could be changed to a “while n1 > 0 or n2 > 0”, which runs at every point in the table until reaching (0, 0). Your hardcoded “ignore” at (0, 0) represents “change nothing in either string” or simply “no change”, so either needs to be explicitly declared as it’s own action or omitted from the actions list as it is implied, because it is present in all possible results of the function

[deadlockofdeath]

Finally something I can wrap my head around.

[shashv]

ngl i feel like you taught me dynamic programming in a single video

[SimGunther]

There was someone on Leetcode who posted a C solution under "Simple solution with prefix/suffix elimination and diagonal match - Faster/less memory than 100%" which decreased the problem size on both sides of the strings in tight loops before running the algorithm with a single array for cost estimates.

[Fortuna]

The thumbnail game is strong with this one. Definitely caught my attention.

[inferrna]

You should try Refal language, which is not only perfect for such tasks, but also is an esoteric one.

[sharathkumark]

Thank you tsoding for making these content, i like this kinda "algorithms exploration" videos (I don't think if the term "algorithm exploration" is a thing)
<3 <3

[blackwinged]

I am kind of impressed that you mentioned CLRS. I have spend way too much time struggling to understand some of its advanced stuff xD

[Lemon_Inspector]

CLRS is an interesting recommendation and it would be a shame if someone just happened to accidentally leave a DRM-free PDF of the entire Introduction to Algorithms, Fourth Edition, freely available to download on the Internet

[jackgoodall]

1:51:25 You should use that animation idea in ded for query replace! It would look so dramatic!

[VACatholic]

Dynamic programming is called dynamic programming because the people doing the research into it wanted funding, and to get it they needed to come up with a name that sounded sexy.

[ramyakmehra]

got the idea from that byte question and animation, imagine getting a png and running it over that and seeing the animation

[caio_c]

I was thinking if it would be possible to do something like this in a simulator for training people, were the controls are mapped in an array and in case of failure in the simulation, there can be an actual step by step of what you could've done to not fail.

[jackgoodall]

Am I wrong in thinking that you don't need to save to the cache after the `n1 == 0` and `n2 == 0` base cases because it will be overwritten by the caller anyway

[Neuer_Alias_erstellen]

why is dynamic programing called dynamic programing
chatGPT:
The term "dynamic programming" was first used by the mathematician Richard Bellman in the 1950s. The name "dynamic programming" was chosen because it refers to the way the algorithm breaks down a problem into smaller subproblems and solves them in a systematic, step-by-step manner. The word "dynamic" refers to the fact that the algorithm works by constantly updating and revising its calculations as it progresses through the problem, rather than simply using a fixed set of calculations or rules.

[ShanyGolan]

How to write in the discord channel? I joined but it's read only.