Commit1939100

authored

Create 2466-count-ways-to-build-good-strings.kt

1 parentfd22564 commit1939100Copy full SHA for 1939100

File tree

+45

-0

lines changed

+45

-0

lines changed

Lines changed: 45 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,45 @@`
	`1`	`+/*`
	`2`	`+* Recursion/DFS + memoization`
	`3`	`+*/`
	`4`	`+classSolution {`
	`5`	`+funcountGoodStrings(low:Int,high:Int,zero:Int,one:Int):Int {`
	`6`	`+val dp=IntArray(high+1) {-1 }`
	`7`	`+val mod=1000000007`
	`8`	`+`
	`9`	`+fundfs(i:Int):Int {`
	`10`	`+if (i> high)`
	`11`	`+return0`
	`12`	`+if (dp[i]!=-1)`
	`13`	`+return dp[i]`
	`14`	`+`
	`15`	`+ dp[i]=if (i>= low)1else0`
	`16`	`+ dp[i]+= dfs(i+ zero)+ dfs(i+ one)`
	`17`	`+ dp[i]= dp[i]% mod`
	`18`	`+`
	`19`	`+return dp[i]`
	`20`	`+ }`
	`21`	`+`
	`22`	`+return dfs(0)`
	`23`	`+ }`
	`24`	`+}`
	`25`	`+`
	`26`	`+/*`
	`27`	`+* Bottom up DP`
	`28`	`+*/`
	`29`	`+classSolution {`
	`30`	`+funcountGoodStrings(low:Int,high:Int,zero:Int,one:Int):Int {`
	`31`	`+val dp=IntArray(high+1)`
	`32`	`+val mod=1000000007`
	`33`	`+`
	`34`	`+ dp[0]=1`
	`35`	`+for (iin1..high) {`
	`36`	`+ dp[i]+=if (i- one>=0) dp[i- one]else0`
	`37`	`+ dp[i]+=if (i- zero>=0) dp[i- zero]else0`
	`38`	`+ dp[i]= dp[i]% mod`
	`39`	`+ }`
	`40`	`+`
	`41`	`+var sum=0`
	`42`	`+for (iin low..high) sum= (sum+ dp[i])% mod`
	`43`	`+return sum`
	`44`	`+ }`
	`45`	`+}`

Comments

(0)