Number of Ways to Form a Target String Given a Dictionary LeetCode solution in C++

1
// Recursion
2
class Solution {
3
  long getWords(vector<string> &words, string &target, int i, int j) {
4
    if (j == target.size()) return 1;
5
    if (i == words[0].size() || words[0].size() - i < target.size() - j) return 0;
6

7
    long count = 0;
8
    for (int idx = 0; idx < words.size(); idx++) {
9
      if (words[idx][i] == target[j]) {
10
        count += getWords(words, target, i + 1, j + 1) % 1000000007;
11
      }
12
    }
13
    count += getWords(words, target, i + 1, j) % 1000000007;
14
    return count % 1000000007;
15
  }
16

17
 public:
18
  int numWays(vector<string> &words, string target) {
19
    return getWords(words, target, 0, 0);
20
  }
21
};
22

23
// memoization but still (85/89)
24
class Solution {
25
  vector<vector<int>> dp;
26

27
  long getWords(vector<string> &words, string &target, int i, int j) {
28
    if (j == target.size()) return 1;
29
    if (i == words[0].size() || words[0].size() - i < target.size() - j) return 0;
30

31
    if (dp[i][j] != -1) return dp[i][j];
32

33
    long count = 0;
34
    for (int idx = 0; idx < words.size(); idx++) {
35
      if (words[idx][i] == target[j]) {
36
        count += getWords(words, target, i + 1, j + 1) % 1000000007;
37
      }
38
    }
39
    count += getWords(words, target, i + 1, j) % 1000000007;
40
    return dp[i][j] = count % 1000000007;
41
  }
42

43
 public:
44
  int numWays(vector<string> &words, string target) {
45
    dp.resize(words[0].size(), vector<int>(target.size(), -1));
46

47
    return getWords(words, target, 0, 0);
48
  }
49
};
50

51
// memoization + optimization (by pre calculating frequency)
52
class Solution {
53
  vector<vector<int>> dp;
54
  vector<vector<int>> freq;
55

56
  long getWords(vector<string> &words, string &target, int i, int j) {
57
    if (j == target.size()) return 1;
58
    if (i == words[0].size() || words[0].size() - i < target.size() - j) return 0;
59

60
    if (dp[i][j] != -1) return dp[i][j];
61

62
    long count = 0;
63
    int curPos = target[j] - 'a';
64
    count += getWords(words, target, i + 1, j);
65
    count += freq[i][curPos] * getWords(words, target, i + 1, j + 1);
66

67
    return dp[i][j] = count % 1000000007;
68
  }
69

70
 public:
71
  int numWays(vector<string> &words, string target) {
72
    dp.resize(words[0].size(), vector<int>(target.size(), -1));
73
    freq.resize(words[0].size(), vector<int>(26, 0));
74

75
    for (int i = 0; i < words.size(); i++) {
76
      for (int j = 0; j < words[0].size(); j++) {
77
        int curPos = words[i][j] - 'a';
78
        freq[j][curPos]++;
79
      }
80
    }
81
    return getWords(words, target, 0, 0);
82
  }
83
};