leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE |
commitb217fbac194589a7e335e0fd4a3f5af91bee7f7d
parentf7d99782c47ebfb547844991de02651a8f586857
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateFri, 5 May 2023 09:16:44 +0200

Daily Problem

Diffstat:
D1639.cpp|----------------------------------------------
AProblems/1456.cpp|+++++++++++++++++++++
AProblems/1639.cpp|++++++++++++++++++++++++++++++++++++++++++++++
MREADME.md|+

4 files changed, 68 insertions(+), 46 deletions(-)

diff --git a/1639.cpp b/1639.cpp

@@ -1,46 +0,0 @@

// Concise way
class Solution {
long dp[1001] = {1, 0};
public:
int numWays(const vector<string> &words, const string &target) {
int n = target.length(), mod = 1e9 + 7;
for (int i = 0; i < words[0].length(); ++i) {
vector<int> count(26);
for (const auto &w : words) count[w[i] - 'a']++;
for (int j = n - 1; j >= 0; --j)
dp[j + 1] += (dp[j] * count[target[j] - 'a']) % mod;
}
return dp[n] % mod;
}
};
// Relatively dump way
class Solution {
int dp[1001][1001] = {0};
int count[1001][26] = {0};
int mod = 1E9 + 7;
int rec(const vector<string> &words, const string &target, int k = 0,
int l = 0) {
if (k >= target.size()) return 1;
if (l >= words[0].size()) return 0;
if (dp[k][l] != -1) return dp[k][l];
long long res = rec(words, target, k, l + 1);
res += ((long long)count[l][target[k] - 'a'] *
rec(words, target, k + 1, l + 1)) %
mod;
return dp[k][l] = res % mod;
}
public:
int numWays(const vector<string> &words, const string &target) {
memset(dp, 0xFF, 1001 * 1001 * sizeof(int)); // init dp to -1
for (int i = 0; i < words.size(); i++)
for (int j = 0; j < words[i].size(); j++) count[j][words[i][j] - 'a']++;
return rec(words, target, 0, 0);
}
};

diff --git a/Problems/1456.cpp b/Problems/1456.cpp

@@ -0,0 +1,21 @@

class Solution {
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
public:
int maxVowels(string s, int k) {
int i, cnt = 0;
for (i = 0; i < k; i++)
if (isVowel(s[i])) cnt++;
int maxi = cnt;
for (; i < s.size(); i++) {
if (isVowel(s[i - k])) cnt--;
if (isVowel(s[i])) cnt++;
maxi = max(maxi, cnt);
}
return maxi;
}
};

diff --git a/Problems/1639.cpp b/Problems/1639.cpp

@@ -0,0 +1,46 @@

// Concise way
class Solution {
long dp[1001] = {1, 0};
public:
int numWays(const vector<string> &words, const string &target) {
int n = target.length(), mod = 1e9 + 7;
for (int i = 0; i < words[0].length(); ++i) {
vector<int> count(26);
for (const auto &w : words) count[w[i] - 'a']++;
for (int j = n - 1; j >= 0; --j)
dp[j + 1] += (dp[j] * count[target[j] - 'a']) % mod;
}
return dp[n] % mod;
}
};
// Relatively dump way
class Solution {
int dp[1001][1001] = {0};
int count[1001][26] = {0};
int mod = 1E9 + 7;
int rec(const vector<string> &words, const string &target, int k = 0,
int l = 0) {
if (k >= target.size()) return 1;
if (l >= words[0].size()) return 0;
if (dp[k][l] != -1) return dp[k][l];
long long res = rec(words, target, k, l + 1);
res += ((long long)count[l][target[k] - 'a'] *
rec(words, target, k + 1, l + 1)) %
mod;
return dp[k][l] = res % mod;
}
public:
int numWays(const vector<string> &words, const string &target) {
memset(dp, 0xFF, 1001 * 1001 * sizeof(int)); // init dp to -1
for (int i = 0; i < words.size(); i++)
for (int j = 0; j < words[i].size(); j++) count[j][words[i][j] - 'a']++;
return rec(words, target, 0, 0);
}
};

diff --git a/README.md b/README.md

@@ -443,6 +443,7 @@ for solving problems.

| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/1438.cpp) |
| 1443 | Medium | [Minimum Time to Collect All Apples in a Tree](Problems/1443.cpp) |
| 1444 | Hard | [Number of Ways of Cutting a Pizza](Problems/1444.cpp) |
| 1456 | Medium | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp) |
| 1462 | Medium | [Course Schedule IV](Problems/1462.cpp) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |
| 1470 | Easy | [Shuffle the Array](Problems/1470.cpp) |