leetcode

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

1639.cpp (1403B)

      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)
     12                 count[w[i] - 'a']++;
     13             for (int j = n - 1; j >= 0; --j)
     14                 dp[j + 1] += (dp[j] * count[target[j] - 'a']) % mod;
     15         }
     16         return dp[n] % mod;
     17     }
     18 };
     19 
     20 // Relatively dump way
     21 class Solution {
     22     int dp[1001][1001] = {0};
     23     int count[1001][26] = {0};
     24     int mod = 1E9 + 7;
     25 
     26     int rec(const vector<string> &words, const string &target, int k = 0, 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'] * rec(words, target, k + 1, l + 1)) % mod;
     33         return dp[k][l] = res % mod;
     34     }
     35 
     36   public:
     37     int numWays(const vector<string> &words, const string &target) {
     38         memset(dp, 0xFF, 1001 * 1001 * sizeof(int)); // init dp to -1
     39         for (int i = 0; i < words.size(); i++)
     40             for (int j = 0; j < words[i].size(); j++)
     41                 count[j][words[i][j] - 'a']++;
     42 
     43         return rec(words, target, 0, 0);
     44     }
     45 };