LeetCode Decode Ways

LeetCode 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 an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.


动态规划题。设s为加密字符串,dp[i]表示s[1,...,i]解密的方案数。如果s[i]\in [1,9],则s[i]可以单独解密,有dp[i]+=dp[i-1];如果s[i-1]s[i]\in [10,26],则s[i]可以和s[i-1]拼起来一起解密,有dp[i]+=dp[i-2]。

DP转移公式如下:

\begin{cases}dp[i] += dp[i-1] & \text{if $s[i] \in [1,9]$}\\dp[i] += dp[i-2] & \text{if $s[i-1]s[i] \in [10,26]$}\\\end{cases}

注意如果0出现在首位则无法解密。

完整代码如下:

class Solution {
public:
	int numDecodings(string s) {
		if (s == "" || s[0] == '0')return 0;
		s = "^" + s;
		int n = s.size();
		vector<int> dp(n, 0);
		dp[0] = dp[1] = 1;
		for (int i = 2; i < n; i++)
		{
			if (s[i] >= '1' && s[i] <= '9')
				dp[i] += dp[i - 1];
			if ((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
				dp[i] += dp[i - 2];
		}
		return dp[n - 1];
	}
};

本代码提交AC,用时8MS。

One thought on “LeetCode Decode Ways

  1. Pingback: LeetCode Decode Ways II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *