Number of Ways to Form a Target String Given a Dictionary

Leetcode Problem:

• Number of Ways to Form a Target String Given a Dictionary

Summary

• This is a problem of forming a target string using given words with certain restrictions.

Approach

• Dynamic programming is used to solve this problem
• The approach involves creating a dictionary to store the frequency of each character in each word and a memoization table to store the intermediate results.

Complexity

• O(n*m*d) where n is the length of the target string, m is the number of words, and d is the number of unique characters in the words.

Explanation

• The solution starts by initializing a dictionary to store the frequency of each character in each word and a memoization table to store the intermediate results
• It then iterates over each word and character in the target string, using the dictionary to get the frequency of the current character and the memoization table to store the intermediate results
• The final result is obtained by summing up the number of ways to form the target string using each word and character.

Solution Code:

class Solution {
public:
    int dict[1001][128];
    int memo[1001][1001];
    int dictN;
    long long getCnt(string& target, int targetIdx, int dictIdx){
        if(target.size() == targetIdx) return 1;
        if(dictIdx >= dictN) return 0;
        if(memo[dictIdx][targetIdx] != -1) return memo[dictIdx][targetIdx];
        long long ret = 0;
        for(int i = dictIdx; i < dictN - (target.size() - targetIdx - 1); i++){
            if(dict[i][target[targetIdx]] == 0) continue;
            ret += getCnt(target, targetIdx+1, i + 1) * dict[i][target[targetIdx]] % 1000000007;
            ret %= 1000000007;
        }
        return memo[dictIdx][targetIdx] = ret;
    }
    int numWays(vector& words, string target) {
        dictN = words[0].size();
        memset(memo, -1, sizeof(memo));
        if(dictN < target.size()) return 0;
        for(int i = 0 ; i < words.size(); i++){
            for(int j = 0 ; j < dictN; j++){
                dict[j][words[i][j]]++;
            }
        }
        return getCnt(target, 0, 0);
    }
};