Dynamic Programming for Counting Vowels
This is an interesting problem: https://leetcode.com/problems/count-sorted-vowel-strings/
Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.
A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.
Example 1:
Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
Example 2:
Input: n = 2 Output: 15 Explanation: The 15 sorted strings that consist of vowels only are ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
Example 3:
Input: n = 33 Output: 66045
Constraints:
1 <= n <= 50
If you look at the hints to this problem, they talk about recursive solutions. I think a DP (Dynamic Programming) suits quite well to it. And the way that I like to do DP is by construction: start by solving the problem for n=1, then use that to solve the problem for n=2, and eventually you get to n=N (the target). The space here will be constant, just holding 5 values for each vowel. When n=1, the solution is given. From that point on, look at the previous solution and do the calculation based on the rules given. The time complexity will be O(5*N), or O(N). Hence O(N)-time, O(1)-space. Code is below, cheers, ACC.
public int CountVowelStrings(int n)
{
int[] dpPrevious = new int[5];
int[] dpCurrent = new int[5];
for (int i = 0; i < dpPrevious.Length; i++) dpPrevious[i] = 1;
int count = 5;
for (int i = 2; i <= n; i++)
{
int partial = 0;
count = 0;
for (int j = 0; j < dpPrevious.Length; j++)
{
partial += dpPrevious[j];
dpCurrent[j] = partial;
count += dpCurrent[j];
dpPrevious[j] = dpCurrent[j];
}
}
return count;
}
Comments
Post a Comment
[γγ¬γΌγ ]