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?
@@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?
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]
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.
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 ?
Why is like after watching your explanations, every problem looks easy!
Can you also cover the follow up question for this problem please?
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.
Was struggling to understand two pointers. This is a great place to start. Thanks
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 !!!!
were you able to get it?
Bro is probably cooked 💀
Could you also address the follow up element of this problem? The one that talks about a stream of query strings "s" coming in.
thats why I came here
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?
@@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?
Best simplest solution
Thank you so much I was able to write my own Java code by using your logic
Pretty neet answer, thanks. The return statement could've been: return i == len(s)
awesome lesson as always!
instead of if else in return statement, write
return i == len(s)
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]
How is this a DP problem ? Can u plz elaborate how this is breaking up into overlapping subproblems and optimal substructure ?
To find the length of the LCS, we need DP. This one is a simple two-pointer solution.
you earned a subscriber today 👍👍.
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.
did u ever figure it out? im wondering the same
Thanks a lot .This video helped me a lot !!
this man is a hero
Thank you so much. You saved my day
Thank you bro.A love from tamil nadu
Thank you NeetCode. One can just return `i == len(s)`
Awesome explanation
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 ?
then j will keep incrementing and eventually stop the loop
thank you so much!
bro are you genius!!
This one killed me for some stupid reason -.-
I'm still Scratching my head, what if it's not in the sequence?
return i == len(s)
concise
Excellent
Bro what if it is wrong order acb,abcdef
he explains it at 1:32
Then it won't be a subsequence, as he explained
It is handled through increment of j
def isSubsequence(s, t):
if all(j in t for j in s):
return True
else:
return False
Thank you very much!