解码方法 II。‘A‘ -> 1,‘B‘ -> 2,...‘Z‘ -> 26。*是1-9,不包含0。
  xaeiTka4h8LY 29天前 38 0

解码方法 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
        }
    }
}

执行结果如下:

2021-10-04:解码方法 II。‘A‘ -> 1,‘B‘ -> 2,...‘Z‘ -> 26。*是1-9,不包含0。给你一个字符串 s ,由数字和 ‘*‘ 字符组成,返回 解码 该字符串的方法

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 29天前 0

暂无评论

推荐阅读
xaeiTka4h8LY