Question

Atlassian | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-18

Answer 1

Images of ques

 

Answer 2

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()];
    }

Answer 3

#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;
}