hey neetcode could you help me figure out why my code give me TLE mod=10**9 + 7 cnt=defaultdict(int) for w in words: for i,c in enumerate(w): cnt[(i,c)]+=1 dp={} def dfs(i,k): if i==len(target): return 1 if k==len(words[0]): return 0 if (i,k) in dp: return dp[(i,k)] dp[(i,k)]=0 for j in range (k,len(words[0])): c=cnt[(j,target[i])] if c>0: dp[(i,k)]+=c*dfs(i+1,j+1) return dp[(i,k)]%mod return dfs(0,0)
I have a little request. when you explain dp problems can you start with the recursive approach, then memoized and then further a tabulisation approach.
I am noticing that almost all recursive problems have a more efficient iterative approach, it would be great if you can also include the iterative approach in videos. Thanks a lot for helping with these problems
Recursive is basically pushing and popping from a stack iteratively. If you cant think about any other iterative solution, just go ahead and try it using stack.
Thank you for the video solution. I got a TLE and couldn't figure out what important optimization lee215 was doing. You pointed it out for me, which was storing the count of every character for each position of the words before recursion. Thanks to you, I will come up with this optimization myself next time.
One kind request. Please use intuitive variable names. Your explanation is top-notch. However, it's really easy to follow along if 'c' was 'current_target_letter' and 'k' was 'col_index'
After solving a bunch of DP problems, DFS solutions come to me very quickly, and the crux in them is optimization. However, the real challenge is to come up with an iterative tabulation solution. It's hard to figure out how to propagate numbers between cells, and I'd like to see a tabulation solution as well to such problems.
Great solution!! just one optimization if cnt[(k,c)] != 0: dp[(i, k)] += cnt[(k,c)] * dfs(i + 1, k + 1) i.e. if cnt[(k,c)] is 0 why bother calling the dfs.
If we loop through the strings to count the matching characters, it timed out for me. I guess it is necessary to precompute the count of characters at each index.
Do we need to have a dict for cnt? Can't we just use an array of len(target)? If the character in w does not match the corresponding character in k, do we need to count that?
The thing I don't understand in this is how are we checking if the character at that particular index in the word matches the character at that index in the target?
The check is done implicitly by using the „cnt“ map. If target[i] = c, then cnt[(k, c)] = 0 if there is no match, i.e. there is no word w with w[k] = c. Otherwise at least one word has character c at index k. Note that we could choose any of them for a new way to form the target string.
![โรงเรียนห้ามรัก โดนจับได้ตาย...!! [เอิร์นไดเม่]](http://i.ytimg.com/vi/4u02Sbr556Q/mqdefault.jpg)
A lot of difficult problems lately.. how are you guys holding up?
Excited to catch up with them all! 😄
Watching your videos helps a lot and this being Exam season in India couldn't use more than an hour on leetcode so directly to your solutions.
by breaking the streak , medium + dp is enough for my brain for 2 days . This and yesterdays one was a nightmare
after this, i went back to 2-sum to re-establish my dominance
hey neetcode could you help me figure out why my code give me TLE
mod=10**9 + 7
cnt=defaultdict(int)
for w in words:
for i,c in enumerate(w):
cnt[(i,c)]+=1
dp={}
def dfs(i,k):
if i==len(target):
return 1
if k==len(words[0]):
return 0
if (i,k) in dp:
return dp[(i,k)]
dp[(i,k)]=0
for j in range (k,len(words[0])):
c=cnt[(j,target[i])]
if c>0:
dp[(i,k)]+=c*dfs(i+1,j+1)
return dp[(i,k)]%mod
return dfs(0,0)
I have a little request. when you explain dp problems can you start with the recursive approach, then memoized and then further a tabulisation approach.
Hmm, he already did so much. May be just do the tabulation part yourself?
I am noticing that almost all recursive problems have a more efficient iterative approach, it would be great if you can also include the iterative approach in videos. Thanks a lot for helping with these problems
Recursive is basically pushing and popping from a stack iteratively. If you cant think about any other iterative solution, just go ahead and try it using stack.
Thank you for the video solution. I got a TLE and couldn't figure out what important optimization lee215 was doing. You pointed it out for me, which was storing the count of every character for each position of the words before recursion. Thanks to you, I will come up with this optimization myself next time.
optimised my code after watching the code upto 6:48, it worked!
One kind request. Please use intuitive variable names. Your explanation is top-notch. However, it's really easy to follow along if 'c' was 'current_target_letter' and 'k' was 'col_index'
I got stucked in the recursion logic. really great explanation Mr. Neetcode :)
So helpful. Thank you. You really did a great job making this problem seem easy.
After solving a bunch of DP problems, DFS solutions come to me very quickly, and the crux in them is optimization. However, the real challenge is to come up with an iterative tabulation solution. It's hard to figure out how to propagate numbers between cells, and I'd like to see a tabulation solution as well to such problems.
Great explanation for a tough problem! Thanks.
Great solution!!
just one optimization
if cnt[(k,c)] != 0:
dp[(i, k)] += cnt[(k,c)] * dfs(i + 1, k + 1)
i.e. if cnt[(k,c)] is 0 why bother calling the dfs.
If we loop through the strings to count the matching characters, it timed out for me. I guess it is necessary to precompute the count of characters at each index.
why multiplied by 2? check timestamp-->6:38
Cam we construct a graph and do dfs
Do we need to have a dict for cnt? Can't we just use an array of len(target)? If the character in w does not match the corresponding character in k, do we need to count that?
great explanation as always !
good one
you saved my day
awesome as always
The thing I don't understand in this is how are we checking if the character at that particular index in the word matches the character at that index in the target?
The check is done implicitly by using the „cnt“ map. If target[i] = c, then cnt[(k, c)] = 0 if there is no match, i.e. there is no word w with w[k] = c. Otherwise at least one word has character c at index k. Note that we could choose any of them for a new way to form the target string.
Just great 😃👍
java version:
class Solution {
private int n;
private int l;
private int m;
private String t;
private static Long[][] dp;
private static int[][] cnt;
private int MOD = (int)1e9 + 7;
public long dfs(int i,int k)
{
if(k == m)
return 1;
if(i == l)
return 0;
if(dp[i][k] != null)
{
return dp[i][k];
}
dp[i][k] = dfs(i + 1,k);
int c = t.charAt(k);
if(cnt[i][c - 'a'] != 0)
{
dp[i][k] += (cnt[i][c - 'a']) * dfs(i + 1,k + 1);
dp[i][k] %= MOD;
}
return dp[i][k];
}
public int numWays(String[] words, String target) {
t = target;
n = words.length;
l = words[0].length();
m = target.length();
dp = new Long[l][m];
cnt = new int[l][26];
for(int i = 0;i < l;i++)
{
for(int j = 0;j < n;j++)
{
cnt[i][words[j].charAt(i) - 'a'] += 1;
}
}
return (int)dfs(0,0);
}
}