文章 224
评论 6
浏览 200773
Dynamic Programming - 91. Decode Ways

Dynamic Programming - 91. Decode Ways

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

思路:

题目意思是有一个只包含数字的字符串,让求出使用给定的映射表来转换,可以有多少种转换的方法,只要是有递归的感觉都可以使用备忘录减少栈空间,优化算法,这是很明显的递归问题,这里使用动态规划求解。状态是:dp[i] numDecodings(i)的返回值,就是字符串s[i...]的合法转换数量。

代码:

go:

func numDecodings(s string) int {

    if s == "" {return 0}

    leng := len(s)
    if leng == 0 { return 1 }
    dp := make([]int, leng+1)
    dp[0] = 1; 
    if s[0] == '0' {
        dp[1] = 0
    } else {
        dp[1] = 1
    }
    
    var prev, next uint8
    for i := 2; i <= leng; i++ {
        next = s[i-1] - '0'
        prev = s[i-2] - '0'
        
        sum := prev * 10 + next
        
        if sum == 0 || next == 0 && prev >= 3 {
            return 0
        } else if next == 0 {
            dp[i] = dp[i-2] // 123 12320
        } else if prev != 0 && sum <= 26 { // 123 -> 1 + 12
            dp[i] = dp[i-1] + dp[i-2]
        } else {
            dp[i] = dp [i-1]  // 1234 = 123
        }
    } 
    
    return dp[leng]
}

标题:Dynamic Programming - 91. Decode Ways
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/08/15/1565880575210.html

Nothing just happens, it's all part of a plan.

取消