[leetocde]Decode Ways

新博文地址：[leetcode]Decode Ways

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.

 被这道题折磨的死去活来。。。递归超时，最后用的DP，但是对DP不是太熟，提交了3次才过

算法思想：

边界：当没有字符（可能为null或者长度为0两种情况），直接返回0即可。

当length == 1时，f(1) = 0(当s == 0时) f(1) = 1(s != 0 )

当length == 2时，f(2) = 2(当s在11~19 || 21 ~26之间) f(2) = 0 （当s < 10 或 s == 30,40,50...90）f(2) = 1(其他情况)

再来看f(n) 

字符串的第一个字母有四种情况，0,1,2,其他，

情况0 : 0 ,f(n) = 0即可

情况1 : 1 那么当第二个字母是0时，f(n) = f(n- 2)其他情况下 f(n) = f(n - 1) + f(n - 2)

情况2: 2 当第二个字母是0,7,8,9时, f(n) = f(n -2)其他情况 f(n) = f(n - 1) + f(n - 2)

情况3，其他情况，f(n) = f(n - 1)

最后返回f(n)

至于代码中，为了与字符串下标统一，我倒着求的，道理是安全一样的

public int numDecodings(String s) {
		if (s == null || s.length() == 0)
			return 0;
		int[] result = new int[s.length()];
		if(s.charAt(s.length() - 1) != '0'){
			result[s.length() - 1] = 1;
		}
		if (s.length() >= 2) {
			int subInt = Integer.valueOf(s.substring(s.length() - 2 ));
			if (subInt > 10 && subInt <= 26 && subInt != 20) {
				result[s.length() - 2] = 2;
			}else if((subInt % 10 == 0 && subInt / 10 > 2) || subInt < 10){
				result[s.length() - 2] = 0;
			}else{
				result[s.length() - 2] = 1;
			}
		}
		for(int i = s.length() - 3 ; i >= 0 ; i--){
			if ((s.charAt(i) == '1' && s.charAt(i + 1) == '0')
					|| (s.charAt(i) == '2' && (s.charAt(i+1) >= '7'
							&& s.charAt(i+1) <= '9' || s.charAt(i+1) == '0'))) {
				result[i] = result[i + 2];
			} else if (s.charAt(i) == '1' || s.charAt(i) == '2') {
				result[i] = result[i + 1]+result[i + 2];
			} else if(s.charAt(i) == '0'){
				result[i] = 0;
			}else{
				result[i] = result[i + 1];
			}
		}
		return result[0];		
	}