[系列文章] leetcode 每日一题1641

发布于 17 天前  29 次阅读


Description

Given an integer n, return the number of strings of length n that consist only of vowels (aeiou) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid is[i] is the same as or comes before s[i+1] in the alphabet.

Solution

动态规划,不妨以数组arr[5]记录可能的排列情况,其中arr[0]表示以a开头的排列,以此类推。对于长度为n+1的一个排列,假设长度n的子问题已经求解,在此基础上,arr[0]~arr[4]均可添加前缀字母aarr[1]~arr[4]可以添加前缀字母e,以此类推......

Code

class Solution {
    int sum(int arr[], int hint) {
        int ans = 0;
        for (int i = hint; i < 5; i++) {
            ans += arr[i];
        }
        return ans;
    }
public:
    int countVowelStrings(int n) {
        int arr[5] = { 1, 1, 1, 1, 1 };
        int count = 1;
        while (count < n) {
            for (int i = 0; i < 5; i++) {
                arr[i] = sum(arr, i);
            }
            count++;
        }
        return sum(arr, 0);
    }
};

一只在互联网躬耕的菜鸟,写代码是热爱,二次元也是,mikoto也是