# 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
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")) ;
End
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. 