91. Decode Ways 解码方式

题目

一个包含 A-Z 字母的消息能够以以下方式进行映射，这种映射称为加密，为了对这些加密后的消息进行解码，首先要将这些数字分组，分组可能有很多中方式，例如 11106 能够被映射为 （1,1,10,6） 或者 （11, 10, 6），注意，不能被映射成 （1,11,06），因为 06 不能被映射成任何字母，06 和 6 是不同的。
要求可能的解码数量。

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

解析

这个问题实际剖析之后，属于爬楼梯问题的特殊版本。从编码可以知道，分组时，要么两个数字一组，要么一个数字一组。1 个数字时，数字区间是 1～9,否则分组无效，两个数字时，数区间是10~29 ，否则分组无效。而一个加密数字的有效分组个数 f（n）= f(n-1) + f(n-2)。f(k) 是否有效，取决于 k 是否满足分组要求。

伪代码

f = [len(s)]int
f[0] = 1
if 1<=value(s[1]) <= 9
  f[1]+=f[0]
if 10<=value(s[0:1])<=26
  f[1]+=1
for i =2;i<len(s);i++
  one =value(s[i])
  two = value(s[i-1:i])
  if 1<=one<=9
    f[i]+=f[i-1]
  if 10<=two<=26
    f[i]+=f[i-2]
return f[len(s)-1]

代码

func numDecodings(s string) int {
    var one, two uint8
    f:=make([]int, len(s)+1)
    f[0]=1
    one = s[0]-'0'
    if one >=1 && one <=9 {
        f[1]=1
    }
    for i:=1;i<len(s);i++ {
        one = s[i]-'0'
        two = (s[i-1]-'0')*10 + (s[i]-'0')
        if one>=1 && one <=9 {
            f[i+1]+=f[i]
        }
        if two>=10 && two <=26 {
            f[i+1]+=f[i-1]
        }
    }
    return f[len(s)]
}

image.png