#
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.