LeetCode -- 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 encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
就是给定1个由数字组成的字符串，按照对应关系（1-A,2-B...）完成解码，共有多少种解码方式。
1. 确定问题范围，也就是s中每一个字符s[i]的取值范围
-s[0]不能为0或大于2
-s中不能连续出现两个0
2. 找规律
在满足取值范围的情况下，设a[i]为s中第i个字符的解码可能数，其中i∈[0,n)
a[0] = 1;
a[1] = s[1] != 0 时为 2 否则为 1;
a[2] :
s[2] 不为0时 a[2] += a[1] ，
s[0]和s[1]可以组成10-26中的一个数时 a[2] += a[0]
因此，对于a[n]，
s[n] != 0 时 ，a[n] += a[n-1] ;
s[n-1]与s[n]可组成10-26 时， a[n] += a[n-2];
对于长度为n的字符串，最后解为a[n-1].
实现代码：
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
就是给定1个由数字组成的字符串，按照对应关系（1-A,2-B...）完成解码，共有多少种解码方式。
1. 确定问题范围，也就是s中每一个字符s[i]的取值范围
-s[0]不能为0或大于2
-s中不能连续出现两个0
2. 找规律
在满足取值范围的情况下，设a[i]为s中第i个字符的解码可能数，其中i∈[0,n)
a[0] = 1;
a[1] = s[1] != 0 时为 2 否则为 1;
a[2] :
s[2] 不为0时 a[2] += a[1] ，
s[0]和s[1]可以组成10-26中的一个数时 a[2] += a[0]
因此，对于a[n]，
s[n] != 0 时 ，a[n] += a[n-1] ;
s[n-1]与s[n]可组成10-26 时， a[n] += a[n-2];
对于长度为n的字符串，最后解为a[n-1].
实现代码：
public class Solution {
public int NumDecodings(string s)
{
if(string.IsNullOrWhiteSpace(s)){
return 0;
}
if(s.Length == 1){
return s == "0" ? 0 : 1;
}
if(s[0] == '0' || s[0] >= '3'&& s[1] == '0'){
return 0;
}
if(s.Length == 2){
return s[1] == '0' || !ok(s[0],s[1]) ? 1 : 2;
}
var arr = new int[s.Length];
arr[0] = 1;
arr[1] = s[1] == '0' || !ok(s[0], s[1]) ? 1 : 2;
for(var i = 2;i < s.Length; i++){
if(s[i-1] == '0' && s[i] == '0'){
return 0;
}
if(s[i] != '0'){
arr[i] += arr[i-1];
}
if(ok(s[i-1], s[i])){
arr[i] += arr[i-2];
}
}
return arr[s.Length-1];
}
private bool ok(char c1 , char c2){
if(c1 == '0'){
return false;
}
if (c1 == '1' || c1 == '2' && c2 <= '6'){
return true;
}
return false;
}
}