找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2153|回复: 4
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Decode Ways】-【刷题第一弹】

[复制链接]

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
发表于 10-22-2014 05:16 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-21-2014 11:57 PM 编辑

快速通道:
https://oj.leetcode.com/problems/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题。设d为S[0...i)字串的decode ways数目, 则d[ i ] = d[i-1] + d[i-2] (i >= 2) .   注意这个递推关系是有前提条件的,当S[i-1] != '0'时, d[i-1]才被加上;当S[i-2, i] 表示的两位数在[10, 26]间时,d[i-2]才被加上。


代码:

  1. int numDecodings(string s) {
  2.     int n = s.size();

  3.     int prev = 1;
  4.     int prev2 = 1;
  5.     int cur = 0;
  6.     for (int i = 1; i <= n; ++i)
  7.     {
  8.         cur = 0;
  9.         if (s[i-1] != '0')
  10.             cur += prev;

  11.         if (i >= 2) {
  12.             int dig = stoi(s.substr(i-2, 2));
  13.             if ((dig >= 10) && (dig <= 26))
  14.                 cur += prev2;

  15.             prev2 = prev;
  16.         }
  17.         prev = cur;
  18.     }
  19.     return cur;
  20. }
复制代码
时间复杂度:O(n)
空间复杂度:O(1)

本帖被以下淘专辑推荐:

10

主题

7

精华

367

积分

高级会员

Rank: 3Rank: 3

积分
367
发表于 11-19-2014 01:25 PM | 显示全部楼层
lz大神!代码好简洁!怎么一遍写出这种代码?
回复 支持 反对

使用道具 举报

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
 楼主| 发表于 11-19-2014 01:49 PM | 显示全部楼层
h2oh2o 发表于 11-19-2014 01:25 PM
lz大神!代码好简洁!怎么一遍写出这种代码?

一遍写出还是有难度的。。我这其实是写完自己polish了的
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表