Decode WaysJun 25 '126747 / 26583
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[i] = dp[i-1] + dp[i-2];
class Solution { public: bool isValid(const string& s, int a) { if (s[a] == '0') return false; else return true; } bool isValid(const string& s, int a, int b) { if (s[a] < '1' || s[a] > '2' || (s[a] == '2' && s[b] > '6')) return false; else return true; } int numDecodings(string s) { int n = s.size(); if (n == 0) return 0; if (s[0] == '0') return 0; vector<int> dp(n, 0); dp[0] = 1; if (s[1] != '0') dp[1]++; if (isValid(s,0,1)) dp[1]++; for (int i = 2; i < n; i++) { if (isValid(s, i)) dp[i] += dp[i-1]; if (isValid(s, i-1, i)) dp[i] += dp[i-2]; } return dp[n-1]; } };
相关推荐
js代码-leetcode 91 DEcode Ways
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
LeetCode 刷题