Chinaunix首页 | 论坛 | 博客
  • 博客访问: 112175
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: C/C++

2014-09-16 15:57:01

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.


*******************************************************************************

分析:

    前i-1共cur种,前i-2共prev种,当把第i个字符加入考虑时,会出现三种情况:

        -- 第i个字符为0,那么第i个加进去以后就是prev种(后面是固定的,所以不会增长)

        -- 第i-1和第i个字符可以合并为一个整体,那么第i个加进去以后就是prev + cur种

        -- 第i-1和第i个字符不能合并为一个整体,那么第i个加进去以后还是cur种


*******************************************************************************

代码:

    int numDecodings(const string &s) {
        if (s.empty() || s[0] == '0') return 0;
        int prev = 0;
        int cur = 1;
        // 长度为n 的字符串,有n+1 个阶梯
        for (size_t i = 1; i <= s.size(); ++i) {
            if (s[i-1] == '0') cur = 0;
            if (i < 2 || !(s[i - 2] == '1' ||
                    (s[i - 2] == '2' && s[i - 1] <= '6')))
                prev = 0;
            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
        return cur;
    }

阅读(410) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册