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 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.

动态规划，找到递推式，找到初始化状态

代码

public class DecodeWays {
	public int numDecodings(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		int N = s.length();
		char[] c = s.toCharArray();

		// init
		int[] dp = new int[N + 1];
		dp[N] = 1;
		dp[N - 1] = c[N - 1] == ‘0‘ ? 0 : 1;

		for (int i = N - 2; i >= 0; --i) {
			dp[i] = (c[i] == ‘0‘ ? 0 : dp[i + 1])
					+ ((c[i] == ‘1‘ || (c[i] == ‘2‘ && c[i + 1] >= ‘0‘ && c[i + 1] <= ‘6‘)) ? dp[i + 2]
							: 0);
		}
		return dp[0];
	}
}

LeetCode | Decode Ways,布布扣,bubuko.com

LeetCode | Decode Ways

原文：http://blog.csdn.net/perfect8886/article/details/20289271