leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README

1639.cpp (1296B)

      1 // Concise way
      2 
      3 class Solution {
      4   long dp[1001] = {1, 0};
      5 
      6 public:
      7   int numWays(const vector<string> &words, const string &target) {
      8     int n = target.length(), mod = 1e9 + 7;
      9     for (int i = 0; i < words[0].length(); ++i) {
     10       vector<int> count(26);
     11       for (const auto &w : words) 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,
     26           int l = 0) {
     27     if (k >= target.size()) return 1;
     28     if (l >= words[0].size()) return 0;
     29     if (dp[k][l] != -1) return dp[k][l];
     30 
     31     long long res = rec(words, target, k, l + 1);
     32     res += ((long long)count[l][target[k] - 'a'] *
     33             rec(words, target, k + 1, l + 1)) %
     34            mod;
     35     return dp[k][l] = res % mod;
     36   }
     37 
     38 public:
     39   int numWays(const vector<string> &words, const string &target) {
     40     memset(dp, 0xFF, 1001 * 1001 * sizeof(int)); // init dp to -1
     41     for (int i = 0; i < words.size(); i++)
     42       for (int j = 0; j < words[i].size(); j++) count[j][words[i][j] - 'a']++;
     43 
     44     return rec(words, target, 0, 0);
     45   }
     46 };