2 minutes
Leetcode 1641
Count Sorted Vowel Strings
Count Sorted Vowel Strings
Head on over here to try the problem for yourself.
Hint says back-tracking, solutions say dynamic programming 😅.
Back-tracking
Algorithm
The goal is to get all sorted combinations of the vowels for a string of length n
. I set up a count
variable outside the functions to ensure it stays out of scope for all the recursive calls. The helper()
function recieves the previous index and remaining charaters. helper()
loops till 4 (because there are 5 vowels). Everytime, n==0
, increment counter
.
Code
public class solution {
int count = 0;
public int countVowelStrings(int n) {
helper(n,0);
return count;
}
public void helper(int n, int index) {
if(n <= 0) {
count++;
return;
}
for(; index < 5; index++) {
helper(n - 1, index);
// index not decremented because same
// letters are valid
}
}
}
Dynamic Programming
Algorithm
The following pattern explains the intuition behind this approach.
a | e | i | o | u | |
---|---|---|---|---|---|
n = 1 | 1 | 1 | 1 | 1 | |
n = 2 | 5 | 4 | 3 | 2 | 1 |
n = 3 | 15 | 10 | 6 | 3 | 1 |
: |
The last string will always be uuuu.. n times
. Every other string will occur count of previous + count of next.
Code
public int countVowelStrings(int n) {
int[] store = new int[5];
for(int i = 0; i < store.length; i++)
store[i] = 1;
// This is the base condition when n = 1
// so we check for n > 1 in the while
while(n-- > 1) {
for(int i = 3; i >= 0; i--) {
store[i] += store[i+1];
// follow the pattern :)
// i was giving i-1 and
// was really confused
}
}
int result = 0;
for(int i = 0; i < store.length; i++)
result += store[i];
return result;
}