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

题目大意 #

一条包含字母 A-Z 的消息通过以下方式进行了编码:

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

给定一个只包含数字的非空字符串,请计算解码方法的总数。

解题思路 #

  • 给出一个数字字符串,题目要求把数字映射成 26 个字母,映射以后问有多少种可能的翻译方法。
  • 这题思路也是 DP。dp[n] 代表翻译长度为 n 个字符的字符串的方法总数。由于题目中的数字可能出现 0,0 不能翻译成任何字母,所以出现 0 要跳过。dp[0] 代表空字符串,只有一种翻译方法,dp[0] = 1。dp[1] 需要考虑原字符串是否是 0 开头的,如果是 0 开头的,dp[1] = 0,如果不是 0 开头的,dp[1] = 1。状态转移方程是 dp[i] += dp[i-1] (当 1 ≤ s[i-1 : i] ≤ 9);dp[i] += dp[i-2] (当 10 ≤ s[i-2 : i] ≤ 26)。最终结果是 dp[n]

代码 #


package leetcode

import (
	"strconv"
)

func numDecodings(s string) int {
	if len(s) == 0 {
		return 0
	}
	dp := make([]int, len(s)+1)
	dp[0] = 1
	if s[:1] == "0" {
		dp[1] = 0
	} else {
		dp[1] = 1
	}
	for i := 2; i <= len(s); i++ {
		lastNum, _ := strconv.Atoi(s[i-1 : i])
		if lastNum >= 1 && lastNum <= 9 {
			dp[i] += dp[i-1]
		}
		lastNum, _ = strconv.Atoi(s[i-2 : i])
		if lastNum >= 10 && lastNum <= 26 {
			dp[i] += dp[i-2]
		}
	}
	return dp[len(s)]
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者