题目描述

image.png

分析

第一个感觉编码就是对给字符串任意切割只要满足在(1,26)就算一种这样推到下来无数个情况

例如
“12” 切割成 {1|2} {12 | } 2
"226" 切割成{2,|2,6} {22,| 6} {2,|26} {226|} 这是无效的

image.png

这有什么规律呀？没看到

每次切割最多2位数，如果剩余数的长度大约2 继续切割这些数据需要解密

image.png

每次切割最多2位数，但是数值不能超过26，如果剩余数的长度大约2 继续切割这些数据需要解密

代码实现

image.png

第一版本纯递归时间

func numDecodings(s string) int {
    return numDecodingsDp(s, len(s))
}

//从大n开始切 dp才是从o开始的 k代表数组剩余的长度
func numDecodingsDp(s string, k int) int {

    if k == 0 {
        return 1
        //如何表示基本字符 'A' -> 1 'B' -> 2 'Z' -> 26
    }
    //字母是从1开始的 非法字符
    begin := len(s) - k

    if s[begin] == 48 {
        return 0
    }
    //10 正确 01 错误

    var step int = 0

    //移动一步
    step = numDecodingsDp(s, k-1)
    //移动二步:条件 大于26
    if k >= 2 {
        //前面2个字符
        temp, _ := strconv.Atoi(s[begin : begin+2])
        if temp <= 26 {
            step += numDecodingsDp(s, k-2)
        }

    }

    fmt.Println(k, begin, s[begin], step)

    return step

}