Is Subsequence - Leetcode 392

0:00 - Drawing Explanation
5:50 - Coding Solution

leetcode 392

#subsequence #python

[vikrampalpatel]

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

[ardev]

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

[josecabrera]

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 !!!!

[navaneethmkrishnan]

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.

[illuna]

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

[nanoname]

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

[buzunoorrishika]

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

[achraftasfaout]

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

[farrukhniaz]

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

[danielsun]

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]

[jaideepsingh]

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

[anutoshghosh]

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.

[sa]

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

[flatmapper]

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

[lamatenzin]

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 ?

[RocketPropelledWombat]

This one killed me for some stupid reason -.-

[yashsolanki]

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

[sriramprasanth]

Bro what if it is wrong order acb, abcdef

[praneeth]

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

else:
return False