{"id":7595,"date":"2020-11-01T00:37:27","date_gmt":"2020-11-01T07:37:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7595"},"modified":"2020-11-01T00:37:58","modified_gmt":"2020-11-01T07:37:58","slug":"leetcode-1641-count-sorted-vowel-strings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1641-count-sorted-vowel-strings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1641. Count Sorted Vowel Strings"},"content":{"rendered":"\n

Given an integer n<\/code>, return the number of strings of length <\/em>n<\/code> that consist only of vowels (<\/em>a<\/code>, <\/em>e<\/code>, <\/em>i<\/code>, <\/em>o<\/code>, <\/em>u<\/code>) and are lexicographically sorted<\/strong>.<\/em><\/p>\n\n\n\n

A string s<\/code> is lexicographically sorted<\/strong> if for all valid i<\/code>, s[i]<\/code> is the same as or comes before s[i+1]<\/code> in the alphabet.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> n = 1\nOutput:<\/strong> 5\nExplanation:<\/strong> The 5 sorted strings that consist of vowels only are [\"a\",\"e\",\"i\",\"o\",\"u\"].<\/code>\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 2\nOutput:<\/strong> 15\nExplanation:<\/strong> The 15 sorted strings that consist of vowels only are\n[\"aa\",\"ae\",\"ai\",\"ao\",\"au\",\"ee\",\"ei\",\"eo\",\"eu\",\"ii\",\"io\",\"iu\",\"oo\",\"ou\",\"uu\"].\nNote that \"ea\" is not a valid string since 'e' comes after 'a' in the alphabet.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 33\nOutput:<\/strong> 66045<\/pre>\n\n\n\n
Solution: DP<\/strong><\/h2>\n\n\n\n
dp[i][j] := # of strings of length i ends with j. <\/p>\n\n\n\n
dp[i][j] = sum(dp[i – 1][[k])  0 <= k <= j<\/p>\n\n\n\n
Time complexity: O(n)
Space complexity: O(n) -> O(1)<\/p>\n\n\n\n
\n
C++\/O(n) Space<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  int countVowelStrings(int n) {\n    \/\/ dp[i][j] = # of strings of length i ends with j\n    vector> dp(n + 1, vector(5, 1));\n    for (int i = 2; i <= n; ++i) {\n      int s = 0;\n      for (int j = 0; j < 5; ++j) {\n        s += dp[i - 1][j];\n        dp[i][j] = s;        \n      }\n    }\n    return accumulate(begin(dp[n]), end(dp[n]), 0);\n  }\n};\n<\/pre>\n\n<\/div>
C++\/O(1) Space<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  int countVowelStrings(int n) {\n    \/\/ dp([i])[j] = # of strings of length i ends with j\n    vector dp(5, 1);\n    for (int i = 2; i <= n; ++i)\n      for (int j = 4; j >= 0; --j)        \n        for (int k = 0; k < j; ++k)\n          dp[j] += dp[k];\n    return accumulate(begin(dp), end(dp), 0);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n","protected":false},"excerpt":{"rendered":"
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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,177],"class_list":["post-7595","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7595","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7595"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7595\/revisions"}],"predecessor-version":[{"id":7597,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7595\/revisions\/7597"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7595"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7595"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7595"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}