题解 | #把数字翻译成字符串#

思路：动态规划

如果没有 0 的话那就很简单了，直接按下面的递推公式遍历就行

dp[i] = dp[i - 1] + (i 和 i - 1 构成的数字是否合法 ? dp[i - 2] : 0);

但是输入的字符串可能会包含非法情况

这种情况一定是非法的

当前为 0，前面的不是 1 或 2.

因为如果不是 1,2 在前面，0 不可能和前面的凑起来也不可能和后面的凑起来，因此遇到这种情况就返回 0.

还有在递推时，当前字符为 0，就不能加上 dp[i - 1].因为单独的一个 0 不能译码

public int solve (String nums) {
  // 排除只有一个 0 的特殊情况
  if ('0' == nums.charAt(0)) {
	return 0;
  }

  int[] dp = new int[nums.length() + 1];
  dp[0] = 1;
  dp[1] = 1;

  Set<Character> validPrefix = new HashSet<>(
	Arrays.asList('1', '2')
  );

  // 递推公式是: dp[i] = (当前字符是否为 0) ? 0 : dp[i - 1] + (i 和 i - 1 构成的数字是否合法 ? dp[i - 2] : 0);
  for (int i = 2; i < nums.length() + 1; i++) {
	int val = Integer.valueOf(nums.substring(i - 2, i));

	dp[i] = (nums.charAt(i - 1) == '0' ? 0 : dp[i - 1]) + 
	  (val <= 26 && nums.charAt(i - 2) != '0' ? dp[i - 2] : 0);

	// 如果当前字符为 0，并且前面的不是 1或 2，那么这一串必定非法直接返回 0
	if (nums.charAt(i - 1) == '0' &&
		!validPrefix.contains(nums.charAt(i - 2))) {
	  return 0;
	}
  }

  return dp[nums.length()];
}