Using Dynamic Programming to Solve a Real-World Problem! | Build a Startup #5

Solving the text difference problem with dynamic programming and JavaScript!

Also, here are the links I mentioned in the video:

[CSDojo]

Hi everyone! Here are the links I mentioned in the video:

[ttff]

TechLead: I know dynamic programming
Joma: Hah! Even more useless

YK: *Hold my beer*

[zmusicseries]

Grammarly is using the same thing in their algorithm.

[BhaveshRaman-xu]

I am 15 and is learning python. The most comfortable channel I feel is CS Dojo

[tsukanomon]

I think thats definitely a case for a future video about: "Over-engineering things"

[WhiteGhost]

Wow just learned dynamic programming and backtracking in class a few days ago. This is def a good study guide!!

[seol]

This guy is great, I loved to see that actual implementation on js too.
He advertises his future startup and does dynamic programming guide at the same time, so cool :)

[abc_cba]

Hey, I see a lot of haters posting hate comments on your video for leaving your job. I find it amazing and inspiring. don't be offended by foolish haters who have nothing to talk positive about. You're an amazing programmer and I enjoy watching your videos .

[ming]

great work as always. Please don't stop updating and let more beginners learn data structure in depth

[rajeshgoswami]

what a clean method of teaching, great job dear

[vidhyakshethra]

Dynamic programming discussed very well in this video. You have really made it seem really easy.

[lipan]

Hey YK!

I'm an iOS developer in Canada, recently I've been looking into applying for large tech companies and your videos have been very helpful! Below is my implementation of your method in swift. Given swift Arrays do not allow for nil values I've used a dictionary (hash table) for memo instead. It'd be great if you or anyone from the community can take a look at my implementation and see if there is anything I can improve on. Also, I was wondering if there is a bottom-up approach, through iteration, to solve this problem like the one you used to solve Fibonacci. Much appreciated!

func lscMemo(first: String, second: String) -> String {

var memo: [[Int]: String] = [:]
var callCount = 0

func lsc(s1: [String], s2: [String], i1: Int, i2: Int) -> String {

callCount += 1

if i1 == s1.count || i2 == s2.count {
return ""
}

if s1[i1] == s2[i2] {
let key = [i1, i2]
if let cachedValue = memo[key] {
return cachedValue
}

let result = s1[i1] + lsc(s1: s1, s2: s2, i1: i1 + 1, i2: i2 + 1)

memo[key] = result
return result

}

let keyA = [i1 + 1, i2]
let keyB = [i1, i2 + 1]

var resultA: String!
var resultB: String!

if let cachedValueA = memo[keyA] {
resultA = cachedValueA
}

else {
resultA = lsc(s1: s1, s2: s2, i1: i1 + 1, i2: i2)
memo[keyA] = resultA
// print("a:", resultA!)

}

if let cachedValueB = memo[keyB] {
resultB = cachedValueB
}

else {
resultB = lsc(s1: s1, s2: s2, i1: i1, i2: i2 + 1)
memo[keyB] = resultB
// print("b:", resultB!)
}

// print("callCount:", callCount)
return resultA.count > resultB.count ? resultA : resultB
}

return lsc(s1: first.map { String ($0) }, s2: second.map { String ($0) }, i1: 0, i2: 0)

// if case insensitive
// return lsc(s1: first.lowercased().map { String ($0) }, s2: second.lowercased().map { String ($0) }, i1: 0, i2: 0)

}

[daviromero]

It seems like a mix of "LCS" and a variation of the "Edit String" algo. (for the second part of the algorithm). Very nice video!

[tw]

Very clear explanation on LCS, thx a lot

[jimkokko]

Thank you for this video!
I have a question though: at 15:19, shouldn't you do

return memo[i1][i2]

instead of

return s[i1] + LCS(s1, s2, i1 + 1, i2 + 1, memo)

?
Because in the first case you wouldn't need to call the LCS function again, as your result would already be stored in memo, so it makes it a tad bit more efficient.

[nora]

thank you, in my programming course we were solving the lcs problem but i didnt get it yet, and now i understand it perfectly with this video

[everyoneloveskayla]

I did this in Python - the only difference is the initialization of the memo.
The i in memo needs to be for the longer word.
Javascript is cool in the way that you won't get any "out of range" constraints like Python.

[akbarnafisa]

keep it up ! need more vids for series like this

[SusilRamarao]

This is an awesome tutorial and explaination... Thanks for the video bro :-)

[hrishikeshsonar]

I love your house! great tutorial as usual though!