Commitc7f0e2d

authored

Update 1220-count-vowels-permutation.kt

1 parent8d9ab23 commitc7f0e2dCopy full SHA for c7f0e2d

File tree

+27

-1

lines changed

+27

-1

lines changed

Lines changed: 27 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,30 @@`
`1`		`-//DP`
	`1`	`+//DP with O(1) space complexity`
	`2`	`+classSolution {`
	`3`	`+funcountVowelPermutation(n:Int):Int {`
	`4`	`+val mod=1_000_000_000+7`
	`5`	`+var prev=LongArray (5) {1L }`
	`6`	`+`
	`7`	`+val a=0`
	`8`	`+val e=1`
	`9`	`+val i=2`
	`10`	`+val o=3`
	`11`	`+val u=4`
	`12`	`+`
	`13`	`+for (jin1 until n) {`
	`14`	`+val new=LongArray (5)`
	`15`	`+ new[a]=0L+ (prev[e]+ prev[i]+ prev[u])% mod`
	`16`	`+ new[e]=0L+ (prev[a]+ prev[i])% mod`
	`17`	`+ new[i]=0L+ (prev[e]+ prev[o])% mod`
	`18`	`+ new[o]=0L+ (prev[i])% mod`
	`19`	`+ new[u]=0L+ (prev[i]+ prev[o])% mod`
	`20`	`+ prev= new`
	`21`	`+ }`
	`22`	`+`
	`23`	`+return (prev.sum()!!% mod).toInt()`
	`24`	`+ }`
	`25`	`+}`
	`26`	`+`
	`27`	`+//DP with O(n) space complexity`
`2`	`28`	`classSolution {`
`3`	`29`	`funcountVowelPermutation(n:Int):Int {`
`4`	`30`	`val mod=1_000_000_000+7`

Comments

(0)