首页 > 代码库 > LeetCode -- Decode Ways

LeetCode -- Decode Ways

2024-09-21 23:52:06   217人阅读

题目描写叙述：
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;
 }
}


LeetCode -- Decode Ways


联系
我们