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 代码
评论