Extra Characters in a String - Leetcode 2707 - Python

[@rohitkumaram]

I think, I need to complete the eligibility to understand, these solutions, 1st DP always pain for me , then Trie. Have marked will try again after few , hopefully that time I could understand this solution.

[@poojababa67]

The explanation is as neet(neat) as it could get!

[@UmarKhan-rb3ts]

The way I went about doing it is the same dp memoisation approach but instead of creating all possible substrings of the string starting the ith index, I iterated over the dictionary words and took the subtring of the given string starting ith index exactly the same length as each dictionary word. However,I don't think there is a great difference in time complexity.

[@kusumjoshi4613]

Can you please share that code

[@shayanshahini642]

@@kusumjoshi4613 This would be code dp = {} def dfs(ind): if ind == len(s): return 0 if ind in dp: return dp[ind] res = 1 + dfs(ind+1) for word in dictionary: if s[ind:ind + len(word)] == word: res = min(res, dfs(ind + len(word))) dp[ind] = res return res return dfs(0)

[@MP-ny3ep]

Great Explanation !

[@rajrajesh1669]

Nice explanation

[@chien-yucode992]

YOU ARE AWESOME

[@light_70]

Thanks :)

[@MartinDeveloper-j9r]

Hi, thanks for posting this video, this is very helpful. Quick question, why do you set dfs(j + 1) in line 33, `res = min(res, dfs(j+1)`. It seems that position, j + 1, is already calculated, so can we call the dp, `dp[j+1]` instead of doing a dfs(j + 1)? Though the if statement will catch it and call the dp. Just curious if there is reason why. Thanks :)

[@pixelbyteee]

Dp[j+1] might not be calculated yet, so we cannot guarantee a solution there... But calling recursively solves that issue

[@abdulrhmankhattab9041]

ty

[@soumyajitchatterjee5822]

Damn. This was a really great solution.

[@ShivangiSingh-wc3gk]

Please can someone correct my understanding Runtime with just recursive 2 ^(n^2) With memoization o n^2 ?

[@rocmewtwo]

slicing substring s[i:j+] also takes O(n), so with memorization is O(n^3). dfs -> n, j inner loop -> n, slicing -> n if using trie, we can reduce the time slice and compare prefixes.

[@Box-iq1zj]

You don't have this leetcode problem in NeetCode All list

[@ZiruiLiu]

I really doubt if these companies will continue to select candidates based on their leetcode coding performance in the future.

[@adamsmith9590]

Why

[@thepriestofvaranasi]

Why

[@Rancha51]

Can you please do Odd Even Jump ? been waiting for that a long time now

[@Nisha.......]

problem number?

[@Rancha51]

@@Nisha....... Leetcode 975

[@Nisha.......]

@@Rancha51 Just tried it using DP, here's the solution: class Solution: def oddEvenJumps(self, arr: List[int]) -> int: n=len(arr) x=[[False,False] for i in range(n)] # odd, even # set both even jump and odd jump of last element to true x[-1][0]=True x[-1][1]=True for i in range(n-2,-1,-1): cur1=[inf,inf] cur2=[-inf,inf] for j in range(i+1,n): if arr[j]>=arr[i] and arr[j]

[@Rancha51]

@@Nisha....... Thanks for the effort, appreciate it. But I am looking for explanation not the code.

[@swastikgorai2332]

can we do it like word break??

[@ahmedashraf3199]

could u consider a c++ solution next time ? ty alot.

[@高进-k1h]

what is definition of your dp，or what is subproblem definition？