# 28.10.2023 [1220. Count Vowels Permutation]
Count of `n` lengths paths according to graph rules `a`->`e`, `e`->(`a`, `i`), etc
28.10.2023
1220. Count Vowels Permutation hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/384
Problem TLDR
Count of n
lengths paths according to graph rules a
->e
, e
->(a
, i
), etc
Intuition
This is a straightforward DFS + memoization dynamic programming problem. Given the current position and the previous character, we know the suffix answer. It is independent of any other factors, so can be cached.
Approach
Let’s write DFS + memo
use Kotlin’s
sumOf
API
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun countVowelPermutation(n: Int): Int {
val vs = mapOf('a' to arrayOf('e'),
'e' to arrayOf('a', 'i'),
'i' to arrayOf('a', 'e', 'o', 'u'),
'o' to arrayOf('i', 'u'),
'u' to arrayOf('a'),
'.' to arrayOf('a', 'e', 'i', 'o', 'u'))
val dp = mutableMapOf<Pair<Int, Char>, Long>()
fun dfs(i: Int, c: Char): Long = if (i == n) 1L else
dp.getOrPut(i to c) { vs[c]!!.sumOf { dfs(i + 1, it) } } %
1_000_000_007L
return dfs(0, '.').toInt()
}
Iterative version:
Another one-liner
Golf version