解码方法 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
}
}
}
执行结果如下：
