当前位置:网站首页>LeetCode 1641. Count the number of Lexicographic vowel strings
LeetCode 1641. Count the number of Lexicographic vowel strings
2022-07-06 16:43:00 【Daylight629】
1641. Count the number of vowel strings in the dictionary
Give you an integer n
, Please return the length of n
、 Only by vowels (a
, e
, i
, o
, u
) Composed and in accordance with Dictionary order The number of strings .
character string s
Press Dictionary order Need to meet : For all that works i
,s[i]
The position in the alphabet is always the same as s[i+1]
Same or in s[i+1]
Before .
Example 1:
Input :n = 1
Output :5
explain : Consisting of only vowels 5 Dictionary order strings are ["a","e","i","o","u"]
Example 2:
Input :n = 2
Output :15
explain : Consisting of only vowels 15 Dictionary order strings are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
Be careful ,"ea" It's not a string according to the meaning of the question , because 'e' Position in the alphabet than 'a' be in the rear
Example 3:
Input :n = 33
Output :66045
Tips :
1 <= n <= 50
Two 、 Method 1
Dynamic gauge , Completely backpack
class Solution {
public int countVowelStrings(int n) {
int[] dp = new int[6];
for (int i = 1; i <= 5; i++) {
dp[i] = 1;
}
for (int j = 2; j <= n; j++) {
for (int i = 2; i <= 5; i++) {
dp[i] += dp[i - 1];
}
}
return dp[1] + dp[2] + dp[3] + dp[4] + dp[5];
}
}
Complexity analysis
Time complexity :O(n).
Spatial complexity :O(1).
3、 ... and 、 Method 2
Permutation and combination , Diaphragm method
class Solution {
public int countVowelStrings(int n) {
return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
}
}
Complexity analysis
Time complexity :O(1).
Spatial complexity :O(1).
边栏推荐
- 第7章 __consumer_offsets topic
- Install Jupiter notebook under Anaconda
- LeetCode 1545. Find the k-th bit in the nth binary string
- Two weeks' experience of intermediate software designer in the crash soft exam
- Remove the border when input is focused
- Chapter 7__ consumer_ offsets topic
- Simply try the new amp model of deepfacelab (deepfake)
- CMake Error: Could not create named generator Visual Studio 16 2019解决方法
- < li> dot style list style type
- Basic principles of video compression coding and audio compression coding
猜你喜欢
LeetCode 1552. Magnetic force between two balls
Simply try the new amp model of deepfacelab (deepfake)
QT implementation window gradually disappears qpropertyanimation+ progress bar
Business system compatible database oracle/postgresql (opengauss) /mysql Trivia
第5章 消费者组详解
Kubernetes cluster deployment
<li>圆点样式 list-style-type
QT style settings of qcobobox controls (rounded corners, drop-down boxes, up expansion, editable, internal layout, etc.)
Discussion on QWidget code setting style sheet
Installation and configuration of MariaDB
随机推荐
Submit several problem records of spark application (sparklauncher with cluster deploy mode)
Kubernetes集群部署
第一章 MapReduce概述
Market trend report, technological innovation and market forecast of China's double sided flexible printed circuit board (FPC)
Oneforall installation and use
JS time function Daquan detailed explanation ----- AHAO blog
Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
第6章 Rebalance详解
Detailed explanation of FLV format
SQL quick start
Li Kou leetcode 280 weekly match
Summary of FTP function implemented by qnetworkaccessmanager
CMake Error: Could not create named generator Visual Studio 16 2019解决方法
Spark独立集群Worker和Executor的概念
LeetCode 1447. Simplest fraction
QT style settings of qcobobox controls (rounded corners, drop-down boxes, up expansion, editable, internal layout, etc.)
第7章 __consumer_offsets topic
Chapter 5 yarn resource scheduler
腾讯面试算法题
Problem - 922D、Robot Vacuum Cleaner - Codeforces