Skip to content

Commit bae82c3

Browse files
liuyuboboboliuyubobobo
committed
1220 added.
1 parent f8d0872 commit bae82c3

File tree

5 files changed

+194
-0
lines changed

5 files changed

+194
-0
lines changed

‎1220-Count-Vowels-Permutation/cpp-1220/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.15)
2+
project(D)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(D main3.cpp)

‎1220-Count-Vowels-Permutation/cpp-1220/main.cpp

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/// Source : https://leetcode.com/problems/count-vowels-permutation/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-10-05
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Memory Search
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
16+
private:
17+
int MOD = 1e9 + 7;
18+
vector<vector<int>> g = {
19+
//a e i o u
20+
{0, 1, 0, 0, 0}, // a
21+
{1, 0, 1, 0, 0}, // e
22+
{1, 1, 0, 1, 1}, // i
23+
{0, 0, 1, 0, 1}, // o
24+
{1, 0, 0, 0, 0} // u
25+
};
26+
27+
public:
28+
int countVowelPermutation(int n) {
29+
30+
vector<vector<int>> dp(5, vector<int>(n, -1));
31+
int res = 0;
32+
for(int i = 0; i < 5; i ++)
33+
res += dfs(i, n - 1, dp), res %= MOD;
34+
return res;
35+
}
36+
37+
private:
38+
int dfs(int cur, int left, vector<vector<int>>& dp){
39+
40+
if(!left) return 1;
41+
if(dp[cur][left] != -1) return dp[cur][left];
42+
43+
int res = 0;
44+
for(int i = 0; i < 5; i ++)
45+
if(g[cur][i])
46+
res += dfs(i, left - 1, dp), res %= MOD;
47+
return dp[cur][left] = res;
48+
}
49+
};
50+
51+
52+
int main() {
53+
54+
cout << Solution().countVowelPermutation(1) << endl;
55+
// 5
56+
57+
cout << Solution().countVowelPermutation(2) << endl;
58+
// 10
59+
60+
cout << Solution().countVowelPermutation(5) << endl;
61+
// 68
62+
63+
return 0;
64+
}

‎1220-Count-Vowels-Permutation/cpp-1220/main2.cpp

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
/// Source : https://leetcode.com/problems/count-vowels-permutation/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-10-06
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Dynamic Programming
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
16+
private:
17+
int MOD = 1e9 + 7;
18+
vector<vector<int>> g = {
19+
//a e i o u
20+
{0, 1, 0, 0, 0}, // a
21+
{1, 0, 1, 0, 0}, // e
22+
{1, 1, 0, 1, 1}, // i
23+
{0, 0, 1, 0, 1}, // o
24+
{1, 0, 0, 0, 0} // u
25+
};
26+
27+
public:
28+
int countVowelPermutation(int n) {
29+
30+
vector<vector<int>> dp(5, vector<int>(n, 0));
31+
for(int i = 0; i < 5; i ++)
32+
dp[i][n - 1] = 1;
33+
34+
for(int j = n - 2; j >= 0; j --)
35+
for(int i = 0; i < 5; i ++){
36+
for(int k = 0; k < 5; k ++)
37+
if(g[i][k])
38+
dp[i][j] += dp[k][j + 1], dp[i][j] %= MOD;
39+
}
40+
41+
int res = 0;
42+
for(int i = 0; i < 5; i ++)
43+
res += dp[i][0], res %= MOD;
44+
return res;
45+
}
46+
};
47+
48+
49+
int main() {
50+
51+
cout << Solution().countVowelPermutation(1) << endl;
52+
// 5
53+
54+
cout << Solution().countVowelPermutation(2) << endl;
55+
// 10
56+
57+
cout << Solution().countVowelPermutation(5) << endl;
58+
// 68
59+
60+
return 0;
61+
}

‎1220-Count-Vowels-Permutation/cpp-1220/main3.cpp

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/// Source : https://leetcode.com/problems/count-vowels-permutation/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-10-06
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Dynamic Programming with Space Optimization
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(1)
14+
class Solution {
15+
16+
private:
17+
int MOD = 1e9 + 7;
18+
vector<vector<int>> g = {
19+
//a e i o u
20+
{0, 1, 0, 0, 0}, // a
21+
{1, 0, 1, 0, 0}, // e
22+
{1, 1, 0, 1, 1}, // i
23+
{0, 0, 1, 0, 1}, // o
24+
{1, 0, 0, 0, 0} // u
25+
};
26+
27+
public:
28+
int countVowelPermutation(int n) {
29+
30+
vector<int> dp(5, 1);
31+
32+
for(int j = n - 2; j >= 0; j --){
33+
vector<int> dp2(5, 0);
34+
for(int i = 0; i < 5; i ++){
35+
for(int k = 0; k < 5; k ++)
36+
if(g[i][k])
37+
dp2[i] += dp[k], dp2[i] %= MOD;
38+
}
39+
dp = dp2;
40+
}
41+
42+
int res = 0;
43+
for(int e: dp)
44+
res += e, res %= MOD;
45+
return res;
46+
}
47+
};
48+
49+
50+
int main() {
51+
52+
cout << Solution().countVowelPermutation(1) << endl;
53+
// 5
54+
55+
cout << Solution().countVowelPermutation(2) << endl;
56+
// 10
57+
58+
cout << Solution().countVowelPermutation(5) << endl;
59+
// 68
60+
61+
return 0;
62+
}

‎readme.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -865,4 +865,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
865865
| 1217 | [Play with Chips](https://leetcode.com/problems/play-with-chips/) | [无] | [C++](1217-Play with Chips/cpp-1217/) | | |
866866
| 1218 | [Longest Arithmetic Subsequence of Given Difference](https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/) | [无] | [C++](1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/) | | |
867867
| 1219 | [Path with Maximum Gold](https://leetcode.com/problems/path-with-maximum-gold/) | [无] | [C++](1219-Path-with-Maximum-Gold/cpp-1219/) | | |
868+
| 1220 | [Count Vowels Permutation](https://leetcode.com/problems/count-vowels-permutation/) | [无] | [C++](1220-Count-Vowels-Permutation/cpp-1220/) | | |
868869
| | | | | | |

0 commit comments

Comments
 (0)