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.

参考: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;
}

 

时间: 2024-10-23 21:46:50

Decode Ways的相关文章

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

[LeetCode] Decode Ways II 解码方法之二

A message containing letters from A-Z is being encoded to numbers using the following mapping way: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers

【LeetCode从零单排】No198.House Robber &amp;amp;&amp;amp;No91.Decode Ways&amp;amp;&amp;amp;139 word break(动态规划典型应用)

1.题目 一道典型的Dynamic Programming的题目. You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security

leetcode难度及面试频率

转载自:LeetCode Question Difficulty Distribution               1 Two Sum 2 5 array sort         set Two Pointers 2 Add Two Numbers 3 4 linked list Two Pointers           Math 3 Longest Substring Without Repeating Characters 3 2 string Two Pointers      

LeetCode总结【转】

转自:http://blog.csdn.net/lanxu_yy/article/details/17848219 版权声明:本文为博主原创文章,未经博主允许不得转载. 最近完成了www.leetcode.com的online judge中151道算法题目.除各个题目有特殊巧妙的解法以外,大部分题目都是经典的算法或者数据结构,因此做了如下小结,具体的解题思路可以搜索我的博客:LeetCode题解 题目 算法 数据结构 注意事项 Clone Graph BFS 哈希表 Word Ladder II

LeetCode All in One 题目讲解汇总(持续更新中...)

终于将LeetCode的免费题刷完了,真是漫长的第一遍啊,估计很多题都忘的差不多了,这次开个题目汇总贴,并附上每道题目的解题连接,方便之后查阅吧~ 如果各位看官们,大神们发现了任何错误,或是代码无法通过OJ,或是有更好的解法,或是有任何疑问,意见和建议的话,请一定要在对应的帖子下面评论区留言告知博主啊,多谢多谢,祝大家刷得愉快,刷得精彩,刷出美好未来- 博主制作了一款iOS的应用"Leetcode Meet Me",里面有Leetcode上所有的题目,并且贴上了博主的解法,随时随地都能

【COCOS2DX-LUA 脚本开发之十】使用LUA CJSON库进行ENCODE与DECODE操作完成对JSON数据转化

本站文章均为 李华明Himi 原创,转载务必在明显处注明:  转载自[黑米GameDev街区] 原文链接: http://www.himigame.com/lua-game/1337.html 本篇介绍如何在lua中对数据进行json的encode与decode,这里Himi采用cjson进行.首先简单介绍下cjson: Lua CJSON 是 Lua 语言提供高性能的 JSON 解析器和编码器,其性能比纯 Lua 库要高 10 到 20 倍.Lua CJSON 完全支持 UTF-8 ,无需依赖

二维码_encode与decode

二维码encode和decode工具类 [html] view plain copy  print? import java.awt.Color;     import java.awt.Graphics2D;     import java.awt.image.BufferedImage;     import java.io.File;     import java.io.IOException;     import java.io.InputStream;     import jav

HEVC代码追踪(十三):解码之decode

// ==================================================================================================================== // Public member functions // ====================================================================================================