1639. Number of Ways to Form a Target String Given a Dictionary

T: O(t_len * w_len)
S: O(w_len*26 + t_len * w_len)

class Solution {
    private static final int MOD = 1_000_000_007;
    public int numWays(String[] words, String target) {
        int[][] count = new int[words[0].length()][26];
        for (String w : words) {
            for (int i = 0; i < w.length(); i++) {
                count[i][w.charAt(i) - 'a']++;
            }
        }
        Integer[][] memo = new Integer[target.length()][words[0].length()];
        return dfs(target, words, 0, 0, memo, count);
    }
    // t is target index, k is word index
    private int dfs(String target, String[] words, int t, int k, Integer[][] memo, int[][] count) {
        if (t == target.length()) {
            return 1;
        }
        if (k == words[0].length()) {
            return 0;
        }
        if (memo[t][k] != null) {
            return memo[t][k];
        }
        char c = target.charAt(t);
        long result = dfs(target, words, t, k+1, memo, count);
        result += (long)dfs(target, words, t+1, k+1, memo, count)*count[k][c-'a'];

        return memo[t][k] = (int)(result%MOD);
    }
}

/***
target[i] = 
str[j][k]
if use
str[any][0~k-1] can't use

abc, abc, abc

t= ac

how to brute force to find?

dfs(target_index, find_in_each_word_k)
find t[0] = a, in each word index k , if k is w_0 -> we can find in these 3 words, words[0] is all a
-> so 3 possible (here is a for for each word)
-> then dfs(t+1, k+1)
=> then can't find "c" in k = 1, so it's dfs(t, k+1)
=> then can find "c" in k = 2... dfs(t+1, k+1), so t reach the len = 2 -> over! return 1
T: O(t_len * w_len * words_array_len) = 10^9 -> will TLE
-> how to reduce it?
avoid to run all words -> using caching! -> so can be count[k][char] = count
so will become result += count[k][char] * dfs(t+1, k+1) (in finding target char case)
not find target char case -> still dfs(t, k+1)
-> T: O(t_len * w_len)


3*dfs(c)
because a has 3 occur...in index 0


dfs(t_index, w_index(k)

 */