解码方法 II。‘A’ -> 1，‘B’ -> 2，…‘Z’ -> 26。是1-9，不包含0。给你一个字符串 s ，由数字和 '’ 字符组成，返回 解码 该字符串的方法 数目 。由于答案数目可能非常大，返回对 10**9 + 7 取余 的结果。力扣639。

递归。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    str := "123*456"
    ret := numDecodings0(str)
    fmt.Println(ret)
}
func numDecodings0(str string) int {
    return f([]byte(str), 0)
}

func f(str []byte, i int) int {
    if i == len(str) {
        return 1
    }
    if str[i] == '0' {
        return 0
    }
    // str[index]有字符且不是'0'
    if str[i] != '*' {
        // str[index] = 1~9
        // i -> 单转
        p1 := f(str, i+1)
        if i+1 == len(str) {
            return p1
        }
        if str[i+1] != '*' {
            num := (str[i]-'0')*10 + str[i+1] - '0'
            p2 := 0
            if num < 27 {
                p2 = f(str, i+2)
            }
            return p1 + p2
        } else { // str[i+1] == '*'
            // i i+1 -> 一起转 1* 2* 3* 9*
            p2 := 0
            if str[i] < '3' {
                //p2 = f(str, i + 2) * (str[i] == '1' ? 9 : 6);
                if str[i] == '1' {
                    p2 = f(str, i+2) * 9
                } else {
                    p2 = f(str, i+2) * 6
                }
            }
            return p1 + p2
        }
    } else { // str[i] == '*' 1~9
        // i 单转 9种
        p1 := 9 * f(str, i+1)
        if i+1 == len(str) {
            return p1
        }
        if str[i+1] != '*' {
            // * 0 10 20
            // * 1 11 21
            // * 2 12 22
            // * 3 13 23
            // * 6 16 26
            // * 7 17
            // * 8 18
            // * 9 19
            p2 := 0
            if str[i+1] < '7' {
                p2 = 2 * f(str, i+2)
            } else {
                p2 = f(str, i+2)
            }
            return p1 + p2
        } else { // str[i+1] == *
            // **
            // 11~19 9
            // 21 ~26 6
            // 15
            p2 := 15 * f(str, i+2)
            return p1 + p2
        }
    }
}

执行结果如下：