[LintCode/LeetCode] Decode Ways [String to Integer]
文章目录
Problem
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.
Example
Given encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.
Note
用parseInt将子字符串转化为int,参见parseInt和valueOf的区别;
然后用动规方法:dp[i]表示字符串s的前i位(0到i-1)包含decode方法的个数。
若前一位i-2到当前位i-1的两位字符串s.substring(i-2, i)对应的数字lastTwo在10到26之间,则当前位dp[i]要加上这两位字符之前一个字符对应的可能性:dp[i-2];
若当前位i-1的字符对应1到9之间的数字(不为0),则当前dp[i]要加上前一位也就是第i-2位的可能性:dp[i-1]。
最后返回对应字符串s末位的动规结果dp[n]。
Solution
updated 2018-9
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) return 0;
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1; //if the first two digits in [10, 26]
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
if (s.charAt(i-1) != '0') dp[i] += dp[i-1]; //XXX5X
int lastTwo = Integer.parseInt(s.substring(i-2, i));
if (lastTwo >= 10 && lastTwo <= 26) dp[i] += dp[i-2]; //XXX10X
}
return dp[n];
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论