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
Solution
dp. 类似于 fibonacci 数列,但是有更多的限制条件
Complexity
Time : O(n); Space : O(1).
Code
public class Solution {
public int numDecodings(String s) {
if (s.length() == 0 || s.charAt(0) == '0') return 0;
int N = s.length();
int f0 = 1, f1 = 1;
for (int i = 1; i < N; ++i) {
if (s.charAt(i) == '0') f1 = 0;
int num = s.charAt(i) - '0' + (s.charAt(i-1) - '0') * 10;
if (num < 10 || num > 26) {
f0 = 0;
}
int tmp = f1;
f1 = f1 + f0;
f0 = tmp;
}
return f1;
}
}