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 encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

给定数字串,判断由字母组成的情况的数量。

简单DP,当前位为0,不可能由前一位转移,若前一位为和当前为组合小于26,则可以用之前两位的状态转移。

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()) return 0;
        vector<int> dp(s.size()+1,0);
        dp[0]=1;
        if(s[0]!='0') dp[1]=1;
        for(int i=1;i<s.size();i++)
        {
            if(s[i]!='0') dp[i+1]+=dp[i];
            if((s[i]>='0' && s[i]<='9' && s[i-1]=='1') || (s[i-1]=='2' && s[i]>='0' && s[i]<='6')) dp[i+1]+=dp[i-1];
        }
        return dp[s.size()];
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 72 Edit Distance DP好题

    Given two words word1 and word2, find the minimum number of steps required to c...

    triplebee
  • Leetcode 70 Climbing Stairs

    You are climbing a stair case. It takes n steps to reach to the top. Each time...

    triplebee
  • HDU4405

    以前不是太会求期望的题目,就是做出来的要是靠一知半解的YY出来,昨天多校又碰到了,于是彻底搞了一把,现在算是撸通了。 具体学习资料查看 http://blog....

    triplebee
  • 程序员面试金典 - 面试题 17.13. 恢复空格(DP+Trie树)

    哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。 像句子"I reset the computer. It still didn’...

    Michael阿明
  • 打卡群刷题总结0929——计算各个位数不同的数字个数

    链接:https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

    木又AI帮
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • 巧解动态规划问题

    前言:最近在力扣刷题,但是之前从没有接触过算法题,有的看答案都看不懂,后来做的题做多了发现有好多类似的题目,所以我打算总结一下规律。

    wsuo
  • LeetCode 801. 使序列递增的最小交换次数(动态规划)

    我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。

    Michael阿明
  • 画解算法:279. 完全平方数

    https://leetcode-cn.com/problems/perfect-squares/

    灵魂画师牧码
  • 打卡群刷题总结0928——整数拆分

    链接:https://leetcode-cn.com/problems/integer-break

    木又AI帮

扫码关注云+社区

领取腾讯云代金券