91. Decode Ways

Problem

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).

Problem Statement

A message containing letters A-Z has been encoded in the following way:

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

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

Solution Approach

• Given a numeric string, the problem asks us to map the numbers to the 26 letters, and then asks how many possible translation methods there are.
• The idea for this problem is also DP. dp[n] represents the total number of ways to translate a string of length n characters. Since the numbers in the problem may include 0, and 0 cannot be translated into any letter, we need to skip it when 0 appears. dp[0] represents the empty string, which has only one translation method, dp[0] = 1. dp[1] needs to consider whether the original string starts with 0. If it starts with 0, dp[1] = 0; if it does not start with 0, dp[1] = 1. The state transition equations are dp[i] += dp[i-1] (when 1 ≤ s[i-1 : i] ≤ 9); dp[i] += dp[i-2] (when 10 ≤ s[i-2 : i] ≤ 26). The final result is dp[n].

Code

package leetcode

func numDecodings(s string) int {
	n := len(s)
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		if s[i-1] != '0' {
			dp[i] += dp[i-1]
		}
		if i > 1 && s[i-2] != '0' && (s[i-2]-'0')*10+(s[i-1]-'0') <= 26 {
			dp[i] += dp[i-2]
		}
	}
	return dp[n]
}