LeetCode - DecodeWays << Back

Take a look at this problem. Now solve it in VDF.

Function numDecodings String s Returns Integer
	String sFirst sSecond
	Integer iSum1 iSum2 iLength
	Move (Length(s)) to iLength
	If (iLength <= 1) Function_Return 1
	Move (Left(s, 1)) to sFirst
	Move (Mid(s, 1, 2)) to sSecond
	Move 0 to iSum1
	Move 0 to iSum2
	If (sFirst="0") Function_Return 0
	If (sFirst="1" Or (sFirst="2" And sSecond<="6")) ;
		Get numDecodings (Remove(s, 1, 2)) to iSum2
	Get numDecodings (Remove(s, 1, 1)) to iSum1
	Function_Return (iSum1 + iSum2)
End_Function

Yuck, too slow. When the input parameter is a long string, it exceeds time limit. Let's use the dynamic programming technique - Memoization

Function ND Integer[] byRef mem String s Returns Integer
	String sFirst sSecond
	Integer iSum1 iSum2 iLength
	Move (Length(s)) to iLength
	If (mem[iLength] <> 0) Function_Return mem[iLength]
	If (iLength = 0) Function_Return 1;
	If (iLength = 1) Function_Return (If(s = "0", 0, 1))
	Move (Left(s,1)) to sFirst
	Move (Mid(s,1,2)) to sSecond
	If (sFirst="0") Function_Return 0
	If (sFirst="1" Or (sFirst="2" And sSecond<="6")) ;
		Get ND (&mem) (Remove(s, 1, 2)) to iSum2
	Else Move 0 to iSum2
	Get ND (&mem) (Remove(s, 1, 1)) to iSum1
	Move (iSum1 + iSum2) to mem[iLength]
	Function_Return (iSum1 + iSum2)
End_Function

Function numDecodings String s Returns Integer
	Integer[] mem
	Integer iResult
	Move (ResizeArray(mem, Length(s) + 1)) to mem
	Get ND (&mem) s to iResult
	Function_Return iResult
End_Function

The answer was good enough, but we can do better. The solution above still consumes quite a bit a stack, and the performance could be better if we can convert the recursive function calls into loop instead. Let's use the dynamic programming technique - Tabulation

Function numDecodings String s Returns Integer
	String sFirst sSecond
	Integer iLength iCurrent
	Integer[] mem
	Move (Length(s)) to iLength
	Move (ResizeArray(mem, iLength + 1)) to mem
	Move 1 to mem[iLength]
	Move (iLength - 1) to iCurrent
	While (iCurrent >= 0)
		Move (Mid(s, 1, iCurrent + 1)) to sFirst
		If (sFirst <> "0") Begin
			If ((iCurrent + 1) < iLength) Begin
				Move (Mid(s, 1, iCurrent + 2)) to sSecond
				If ((sFirst = "1") Or (sFirst = "2" and sSecond <= "6")) ;
					Add mem[iCurrent + 2] to mem[iCurrent]
			End
			Add mem[iCurrent + 1] to mem[iCurrent]
		End
		Decrement iCurrent
	Loop
	Function_Return mem[0]
End_Function

The answer was better, but we can do better. The solution is now using loop instead of recursive calls. However we don't need to keep track (tabulation) of all the past combinations. We only need the last two.

Function numDecodings String s Returns Integer
	String sFirst sSecond
	Integer iLength iPrev iPrevPrev iNow
	Move (Length(s)) to iLength
	Move 1 to iPrev
	Move 0 to iPrevPrev
	Move 0 to iNow
	Move (iLength - 1) to iCurrent
	While (iCurrent >= 0)
		Move 0 to iNow
		Move (Mid(s, 1, iCurrent + 1)) to sFirst
		If (sFirst <> "0") Begin
			If ((iCurrent + 1) < iLength) Begin
				Move (Mid(s, 1, iCurrent + 2)) to sSecond
				If ((sFirst = "1") Or (sFirst = "2" and sSecond <= "6")) ;
					Add iPrevPrev to iNow
			End
			Add iPrev to iNow
		End
		Move iPrev to iPrevPrev
		Move iNow to iPrev
		Decrement iCurrent
	Loop
	Function_Return iNow
End_Function

Finally, no more recursive calls, no more extra memory needed.