2021-02-17：规定1和A对应、2和B对应、3和C对应...26和Z对应，那么一个数字字符串比如"111”就可以转化为:"AAA"、"KA"和"AK"。给定一个只有数字字符组成的字符串str，请问有多少种转化结果？
福哥答案2021-02-17：
自然智慧即可。
1.递归。有代码。
2.动态规划。有代码。
代码用golang编写，代码如下：
package main
import "fmt"
func main() {
str := "7210231231232031203123"
fmt.Println("1.递归：", number1(str))
fmt.Println("2.动态规划：", number2(str))
}
func number1(str string) int {
if len(str) == 0 {
return 0
}
return process1(str, 0)
}
func process1(str string, index int) int {
strLen := len(str)
if strLen == index { //1
return 1
}
if str[index] == '0' {
return 0
}
ret := process1(str, index+1)
if index+1 < strLen && (str[index] == '1' || (str[index] == '2' && str[index+1] <= '6')) {
ret += process1(str, index+2)
}
return ret
}
func number2(str string) int {
strLen := len(str)
if strLen == 0 {
return 0
}
dp := make([]int, strLen+1)
dp[strLen] = 1 //1
for i := strLen - 1; i >= 0; i-- {
if str[i] == '0' {
continue
}
dp[i] = dp[i+1]
if i+1 < strLen && (str[i] == '1' || (str[i] == '2' && str[i+1] <= '6')) {
dp[i] += dp[i+2]
}
}
return dp[0]
}
执行结果如下：
左神java代码
评论
