C++ code: typedef long long ll; class Solution { public: int mod = 1e9+7; int numWays(vector& words, string target) { int diclen = words[0].size(); int n = target.size(); vector columns(diclen,vector(26,0)); for(int ind = 0;ind=0;t_ind--){ vector temp(diclen+1,0); for(int col = diclen-1;col>=0;col--){ temp[col] += temp[col+1]%mod; int tempind = target[t_ind]-'a'; if(columns[col][tempind]){ temp[col] = (temp[col]%mod + (columns[col][tempind]%mod * dp[col+1]%mod)%mod)%mod; } } dp = temp; } return dp[0]; } }; Python code: def numWays(self, words: List[str], target: str) -> int: diclen = len(words[0]) columns = [[0]*26 for _ in range(diclen)] alphind = {c:i for i,c in enumerate('abcdefghijklmnopqrstuvwxyz')} # print(alphind) for ind in range(diclen): for w in words: columns[ind][alphind[w[ind]]] += 1 n = len(target) dp = [1]*(diclen+1) for row in range(n-1,-1,-1): temp = [0]*(diclen+1) for col in range(diclen-1,-1,-1): temp[col] += temp[col+1]%mod tempind = alphind[target[row]] if columns[col][tempind]: temp[col] = (temp[col]%mod + (columns[col][tempind]%mod*dp[col+1]%mod)%mod)%mod dp = temp return dp[0] Ask if any queston
@@codestorywithMIK yeah bro don't be apologetic. I can understand you have a full time job and also you're preparing a full length video everyday for us. That itself is a great thing. So I can bear with you happily 🙂
sir please check where is the issue class Solution { public: int numWays(vector& words, string target) { int m = target.length(); int k = words[0].size(); int MOD = 1e9 + 7;
I used to quit these Hard problems before. Thank you so much MIK.
This is where magic happens : Hard is made Easy
Damn you are extremely hard working
thanks sir!!
Amazing explanation
Thank u sir
I saw solutions where they have used 1D dp , if possible could you try to come up with a video on that. And all the best !!
Hmm i am curious. I will look at that too for sure. Thanks for watching Akif ❤️❤️❤️
C++ code:
typedef long long ll;
class Solution {
public:
int mod = 1e9+7;
int numWays(vector& words, string target) {
int diclen = words[0].size();
int n = target.size();
vector columns(diclen,vector(26,0));
for(int ind = 0;ind=0;t_ind--){
vector temp(diclen+1,0);
for(int col = diclen-1;col>=0;col--){
temp[col] += temp[col+1]%mod;
int tempind = target[t_ind]-'a';
if(columns[col][tempind]){
temp[col] = (temp[col]%mod + (columns[col][tempind]%mod * dp[col+1]%mod)%mod)%mod;
}
}
dp = temp;
}
return dp[0];
}
};
Python code:
def numWays(self, words: List[str], target: str) -> int:
diclen = len(words[0])
columns = [[0]*26 for _ in range(diclen)]
alphind = {c:i for i,c in enumerate('abcdefghijklmnopqrstuvwxyz')}
# print(alphind)
for ind in range(diclen):
for w in words:
columns[ind][alphind[w[ind]]] += 1
n = len(target)
dp = [1]*(diclen+1)
for row in range(n-1,-1,-1):
temp = [0]*(diclen+1)
for col in range(diclen-1,-1,-1):
temp[col] += temp[col+1]%mod
tempind = alphind[target[row]]
if columns[col][tempind]:
temp[col] = (temp[col]%mod + (columns[col][tempind]%mod*dp[col+1]%mod)%mod)%mod
dp = temp
return dp[0]
Ask if any queston
Java:
class Solution {
private int m;
private int k;
private int dp[][];
private int mod;
public int numWays(String[] words, String target) {
this.m = target.length();
this.k = words[0].length();
this.mod = 1000000007;
this.dp = new int[1001][1001];
//dp[i][j] = total ways to form target of length i using dicts word of each length j
long freq[][] = new long[26][k];
for(int col=0; col
Maine recursion+memo se submit Kiya to TLE a raha hai
Please share the code
And make sure you pass parameters by reference
class Solution {
public:
int m,k;
int t[1001][1001];
int solve(vector &freq, string target,int i,int j){
if(i==m) return 1;
if(j==k) return 0;
const int MOD=1e9+7;
if(t[i][j]!=-1) return t[i][j];
int not_taken=solve(freq,target,i,j+1)%MOD;
int taken=(solve(freq,target,i+1,j+1)*freq[target[i]-'a'][j])%MOD;
return t[i][j]=(not_taken+taken)%MOD;
}
int numWays(vector& words, string target) {
m=target.length();
k=words[0].length();
vector freq(26,vector(k));
for(int col=0;col
Try passing target by reference
Thanks it worked
First view
❤
And I think the REMAINDER you won't forget.
Hi Mani,
I hope it’s fine, if the video comes tomorrow morning. Actually the editing is remaining.
Thanks for your patience ❤️❤️❤️
@@codestorywithMIK Thanks a lot that you remember me and my remainder.
Thanks in advance for listening to my request.
Apologies for the delay brother.
Hope you will understand.
You have been extremely patient and I will always remember this. ❤️❤️❤️
@@codestorywithMIK yeah bro don't be apologetic. I can understand you have a full time job and also you're preparing a full length video everyday for us.
That itself is a great thing. So I can bear with you happily 🙂
Means a lot ❤️❤️❤️
Please feel free to connect with me on LinkedIn
sir please check where is the issue
class Solution {
public:
int numWays(vector& words, string target) {
int m = target.length();
int k = words[0].size();
int MOD = 1e9 + 7;
vector freq(26, vector(k));
for(int col = 0; col < k; col++) {
for(string &word : words) {
freq[word[col] - 'a'][col]++;
}
}
vector dp(m + 1, vector(k + 1, 0));
dp[m][k] = 1;
for(int i = m - 1; i >= 0; i--) {
for(int j = k - 1; j >= 0; j--) {
int not_taken = dp[i][j + 1] % MOD;
int taken = (freq[target[i] - 'a'][j] * dp[i + 1][j + 1]) % MOD;
dp[i][j] = (not_taken + taken) % MOD;
}
}
return dp[0][0];
}
};
What output you are getting ?
can you make community on telegram
I am soon planning that. 🙌❤️