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.
public class Solution { public int numDecodings(String s) { if (s.length() == 0) { return 0; } int[] dp = new int[s.length()+1]; dp[0] = 1; if (isValid(s.substring(0, 1))) { dp[1] = 1; } else { dp[1] = 0; } for (int i = 2; i <= s.length(); i++) { if (isValid(s.substring(i-1, i))) { dp[i] = dp[i-1]; } if (isValid(s.substring(i-2, i))) { dp[i] += dp[i-2]; } } return dp[s.length()]; } private boolean isValid(String substring) { if (substring.charAt(0) == '0') { return false; } int parseInt = Integer.parseInt(substring); return parseInt>0 && parseInt<27; } }
相关推荐
js代码-leetcode 91 DEcode Ways
Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid ...
Decode Ways Distinct Subsequences Word Break Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 ...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 ...Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
加油站 leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167....2107/03/06 15.3 总和,16.3 ...91.Decode Ways, 96.Unique Binary Search Tree, 120.Triangle, 139.Word Break, 152.Maximum Produ
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 ...我经常在递归的结束地方忘记return!...091:Decode Ways 简单的一维DP,用额外数组O(n)即可。 139,1
扩展矩阵leetcode interview-algorithm leetCode 待解决 上楼梯问题 how many ways to decode this message @leetCode 91
Python is an easy-to-learn and extensible programming language that allows secret agents to work with a wide variety of data in a number of ways. It gives beginners a simple way to start programming, ...
题目 一条包含字母 A-Z 的消息通过以下方式进行了编码: ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串...链接:https://leetcode-cn.com/problems/decode-ways 思路 这个题有点像爬楼梯,但是
Gather, analyze, and decode data to reveal hidden facts using Python, the perfect tool for all aspiring secret agents About This Book Discover the essential features of Python programming: statements...
There’s basically two ways to measure this: same-bitrate (e.g. a 500kbps VP8 file vs. a 500kbps VP9 file, where the VP9 file likely looks much better), or same-quality (e.g. a VP8 file with SSIM=...
1997 - 2003 Sergio A....and fixed it. Some minor bugs that I don‘t remember fixed.- Added MIME-compliant base64 support (not for use by now). Added examples.0.9.2.1b- Fixed a bug when send a mail and ...
Yes, this possibly is one of the worst ways to do this, //but RAM is at a premium here, and this works for most of the cases. int ICACHE_FLASH_ATTR openConn(const char *streamHost, const char *...