lc1639

Considering words = [“acca”,”bbbb”,”caca”], target = “aba”

dp[1][2] means the result for target “ab” and words=[“acc”, “bbb”, “cac”]

To calculate dp[i][j]:

1. dp[i][j] = dp[i][j – 1]. This means when words has is 1 letter small, the result to cover target[0,…,i]. In this case, dp[2][3] = dp[2][2]

2. In words array, for j column, when there is x number of letters which equals to target[i]. It is ‘a’ for this case. Then needs to add dp[i-1][j-1] * x. For dp[2][3], this part is result of [“acc”, “bbb”, “cac”], “ab”, multiplying number of ‘a’ in column 3, which is 2.

For each column of the words, create a count[column][26] to mark the number of letters in that column.