Decode Ways

简介: A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 .

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.

参考:http://www.cnblogs.com/TenosDoIt/p/3451920.html

分析:需要注意的是,如果序列中有不能匹配的0,那么解码方法是0,比如序列012 、100(第二个0可以和1组成10,第三个0不能匹配)。递归的解法很容易,但是大集合会超时。转换成动态规划的方法,假设dp[i]表示序列s[0...i-1]的解码数目,动态规划方程如下:                                                                                                                                                              

  • 初始条件: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月前
|
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
字母A到Z分别和1到26的数字一一对应,给定一串用字符表示的数字,将数字串从不同位置拆开,每一个数字都对应一个字符,如此构成了一个字母字符串. 从不同的位置拆分数字字符串,可以得到不同的字母字符串,问一共有多少种有效的拆分方式.
53 0
LeetCode 91. Decode Ways
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