【LeetCode】 1641. Count Sorted Vowel Strings

Description

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.

給予一正整數 n，回傳所有只包含母音 (a, e, i, o, u)、按照字典順序排序的字串數量。

一個字串 s 如果是按字典順序排序，表示對於所有有效的 i, s[i] 來說，s[i+1] 一定和他相同或是在它之前。

• 限制：
  1 <= n <= 50

Example:

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

Solution

• 先利用枚舉來觀察規律
  • n = 1 的時候只有 aeiou
  • n = 2 時
    • a 有 5
    • e 有 4
    • i 有 3
    • o 有 2
    • u 有 1
  • n = 3 時
    • a 有 15 (15 - 0)
    • e 有 10 (15 - 5)
    • i 有 6 (15 - 5 - 4)
    • o 有 3 (15 - 5 - 4 - 3)
    • u 有 1 (15 - 5 - 4 - 3 - 2)
• 可以發現規律是上一次的總和(sum of 0~5) - 上一次到自己為止的總和(sum of 0~i)

Code

class Solution {
public:
    int sumTable(int* table, int size)
    {
        int sum = 0;
        
        for(int i = 0; i < size; i++)
            sum += table[i];
        
        return sum;
    }
    int countVowelStrings(int n) {
        if(n == 1)
            return 5;
        /*
        5 aa ae ai ao au
        4    ee ei eo eu
        3       ii io iu
        2          oo ou
        1             uu
        */
        int table[] = {5, 4, 3, 2, 1};
        int preTable[] = {0, 5, 9, 12, 14};
        
        for(int i = 2; i < n; i++)
        {
            int sum = sumTable(table, 5);
            for(int j = 0; j < 5; j++)
            {
                table[j] = sum - preTable[j];
                preTable[j] = sumTable(table, j);
            }
        }
        
        return sumTable(table, 5);
    }
};

tags: LeetCode C++