leetcode

0 // Concise way

1

2 class Solution {

3 long dp[1001] = {1, 0};

4

5 public:

6 int numWays(const vector<string> &words, const string &target) {

7 int n = target.length(), mod = 1e9 + 7;

8 for (int i = 0; i < words[0].length(); ++i) {

9 vector<int> count(26);

10 for (const auto &w : words)

11 count[w[i] - 'a']++;

12 for (int j = n - 1; j >= 0; --j)

13 dp[j + 1] += (dp[j] * count[target[j] - 'a']) % mod;

14 }

15 return dp[n] % mod;

16 }

17 };

18

19 // Relatively dump way

20 class Solution {

21 int dp[1001][1001] = {0};

22 int count[1001][26] = {0};

23 int mod = 1E9 + 7;

24

25 int rec(const vector<string> &words, const string &target, int k = 0, int l = 0) {

26 if (k >= target.size()) return 1;

27 if (l >= words[0].size()) return 0;

28 if (dp[k][l] != -1) return dp[k][l];

29

30 long long res = rec(words, target, k, l + 1);

31 res += ((long long)count[l][target[k] - 'a'] * rec(words, target, k + 1, l + 1)) % mod;

32 return dp[k][l] = res % mod;

33 }

34

35 public:

36 int numWays(const vector<string> &words, const string &target) {

37 memset(dp, 0xFF, 1001 * 1001 * sizeof(int)); // init dp to -1

38 for (int i = 0; i < words.size(); i++)

39 for (int j = 0; j < words[i].size(); j++)

40 count[j][words[i][j] - 'a']++;

41

42 return rec(words, target, 0, 0);

43 }

44 };