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

• 初始条件：dp[0] = 1, dp[1] = (s[0] == '0') ? 0 : 1
• dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1]可以表示字母 ？ dp[i-2] : 0 )， 其中第一个分量是把s[0...i-1]末尾一个数字当做一个字母来考虑，第二个分量是把s[0...i-1]末尾两个数字当做一个字母来考虑

C++实现代码：（为什么dp要有n+1的长度呢，除了s[0]以外，每次s[i]与两个元素有关，所以使用dp[0]记为1，s[0]的记录存放在dp[1]中。

#include<iostream>
#include<string>
using namespace std;

class Solution
{
public:
int numDecodings(string s)
{
if(s.empty())
return 0;
int n=s.size();
int dp[n+1];
//dp[i]表示s[0...i-1]的解码方法数目
dp[0]=1;
if(s[0]=='0')
dp[1]=0;
else
dp[1]=1;
int i;
for(i=2;i<n+1;i++)
{
if(s[i-1]=='0')
dp[i]=0;
else
dp[i]=dp[i-1];
if((s[i-2]=='2'&&s[i-1]<='6')||(s[i-2]=='1'))
dp[i]+=dp[i-2];
}
return dp[n];
}
};

int main()
{
Solution s;
cout<<s.numDecodings(string("123456"))<<endl;
}

|
16天前
|
JavaScript
Invalid project name: “Philosophers-Stone“Warning: name can no longer contain capital letters
Invalid project name: “Philosophers-Stone“Warning: name can no longer contain capital letters
9 0
|
9月前
|
JSON 数据格式
JsonParseException: Unexpected character (‘ï‘ (code 239)): was expecting comma to separate Object
JsonParseException: Unexpected character (‘ï‘ (code 239)): was expecting comma to separate Object
96 0
LeetCode 91. Decode Ways

53 0
Data Structures and Algorithms (English) - 7-8 File Transfer（25 分）
Data Structures and Algorithms (English) - 7-8 File Transfer（25 分）
92 0
HDOJ 1092 A+B for Input-Output Practice (IV)
HDOJ 1092 A+B for Input-Output Practice (IV)
102 0
HDOJ 1090 A+B for Input-Output Practice (II)
HDOJ 1090 A+B for Input-Output Practice (II)
79 0
HDOJ 1091 A+B for Input-Output Practice (III)
HDOJ 1091 A+B for Input-Output Practice (III)
87 0
HDOJ 1093 A+B for Input-Output Practice (V)
HDOJ 1093 A+B for Input-Output Practice (V)
82 0
HDOJ 1089 A+B for Input-Output Practice (I)
HDOJ 1089 A+B for Input-Output Practice (I)
100 0
HDOJ 1096 A+B for Input-Output Practice (VIII)
HDOJ 1096 A+B for Input-Output Practice (VIII)
87 0