leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1639.cpp (1403B)

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 };