Is Subsequence - Leetcode 392

[@sanchayeetasir]

Why is like after watching your explanations, every problem looks easy!

[@josecabrera7947]

Dude mark my words if I get this internship with google or amazon in Seattle for summer 2023 I will personally take you to dinner !!!!

[@servantofthelord8147]

were you able to get it?

[@illu1na]

Can you also cover the follow up question for this problem please?

[@a4rdev]

Was struggling to understand two pointers. This is a great place to start. Thanks

[@navaneethmkrishnan6374]

A lot of people ask why the question is given under the DP tag. This is because to find the length of the longest common subsequence, we need DP.

[@nanoname5226]

Could you also address the follow up element of this problem? The one that talks about a stream of query strings "s" coming in.

[@vasujhawar.6987]

thats why I came here

[@jayjw1]

I'm not sure if there's more to it, but wouldn't you just check if s > t: return False automatically because s can't be a subsequence if it's larger than the entirety of t?

[@gamba3685]

@@jayjw1 No, the follow-up element isnt talking about any specific s, it's talking about how to be more efficient if there are multiple s being sent to our function, how can we evaluate each s in an efficient way?

[@farrukhniaz3218]

instead of if else in return statement, write return i == len(s)

[@buzunoorrishika8690]

Thank you so much I was able to write my own Java code by using your logic

[@achraftasfaout2960]

Pretty neet answer, thanks. The return statement could've been: return i == len(s)

[@fanyang9777]

awesome lesson as always!

[@jaideepsingh7955]

How is this a DP problem ? Can u plz elaborate how this is breaking up into overlapping subproblems and optimal substructure ?

[@navaneethmkrishnan6374]

To find the length of the LCS, we need DP. This one is a simple two-pointer solution.

[@anutoshghosh7893]

In the two pointer approach, I did not understand one thing the ordering also has to be checked in a subsequence which is missing for the problem in the testcases, for instance here s = "acg" and t = "ahbgdc", they are considering s as a subsequence of t which should not be so, as the ordering is not maintained, although all elements are present from s in t.

[@ryanbaker7419]

did u ever figure it out? im wondering the same

[@danielsun716]

DP solution: It is easy to think of this if you finished 10. regular expression matching. def isSubsequence(self, s: str, t: str) -> bool: if len(s) > len(t): return False dp = [[False] * (len(t) + 1) for _ in range(len(s) + 1)] for j in range(len(t) + 1): dp[len(s)][j] = True for i in range(len(s) - 1, -1, -1): for j in range(len(t) - 1, -1, -1): match = s[i] == t[j] if match: dp[i][j] = dp[i + 1][j + 1] else: dp[i][j] = dp[i][j + 1] return dp[0][0]

[@iosifpuha6114]

this man is a hero

[@cryptohamsterx]

bro are you genius!!

[@flatmapper]

Thank you NeetCode. One can just return `i == len(s)`

[@arunimachakraborty1175]

Thank you so much. You saved my day

[@akshatverma838]

you earned a subscriber today 👍👍.

[@sa25078]

Thanks a lot .This video helped me a lot !!

[@krateskim4169]

Awesome explanation

[@bilalmohammad4242]

Thank you very much!

[@lamatenzin8756]

but wouldn't the while loop keeping looping endlessly if i is never incremented? because your'e only incrementing i if s[i] = s[j]. what if it never equals ?

[@srx2106]

then j will keep incrementing and eventually stop the loop

[@love2code_official]

Thank you bro.A love from tamil nadu

[@RocketPropelledWombat]

This one killed me for some stupid reason -.-

[@elias043011]

return i == len(s) concise

[@yashsolanki069]

I'm still Scratching my head, what if it's not in the sequence?

[@sanjeevacham2400]

Excellent

[@sriramprasanth3390]

Bro what if it is wrong order acb,abcdef

[@Track-Tor]

he explains it at 1:32

[@DanhWasHere]

Then it won't be a subsequence, as he explained

[@kanikasaxena8603]

It is handled through increment of j

[@praneeth8380]

def isSubsequence(s, t): if all(j in t for j in s): return True else: return False

[@joshua_dlima]

thank you so much!