0 like 0 dislike
1,252 views
| 1,252 views

0 like 0 dislike

Images of ques

by Expert (46,090 points)
0 like 0 dislike

For Q3 (Java):
Use dp.
`dp[i][j]` = the number of ways to form substsring of goal from length `0...j` with the first `i` column

``````    public int solve(String[][] words, String goal){
int M = (int)1e9+7;
long[] dp = new long[goal.length()+1];
dp[0]=1;
for (int i = 0; i < words[0].length(); i++){
int[] count = new int[26];
for (String s : words){
count[s.charAt(i)-'a']++;
}
for (int j = goal.length(); j >= 1; j--){
dp[j]+=dp[j-1]*count[goal.charAt(j-1)-'a']%M;
}
}
return (int)dp[goal.length()];
}``````
by Expert (46,090 points)
0 like 0 dislike
``````#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int dp[3001][3002];

long long solve(int i,string &target,int prev,unordered_map<char,vector<int>>&mp){
if(i == target.size()) return 1;
if(dp[prev+1][i] != -1) return dp[prev+1][i];

long long ans = 0;

auto &vec = mp[target[i]];
for(auto idx : vec){
if(idx > prev)
ans = (ans + solve(i+1,target,idx,mp)) % mod;
}

return dp[prev+1][i] = ans;
}

int main() {
int n; cin>>n;
vector<string> arr(n);
for(auto &it : arr) cin>>it;
string target; cin>>target;
unordered_map<char,vector<int>> mp;
for(auto &str : arr){
for(int i=0;i<str.size();i++){
mp[str[i]].push_back(i);
}
}
memset(dp,-1,sizeof dp);
cout<<solve(0,target,-1,mp)<<endl;
}``````
by Expert (46,090 points)