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.

原问题链接：https://leetcode.com/problems/decode-ways/

 

问题分析

　　从前面问题的描述里看，我们给定的一个纯数字的字符串它需要根据对应的映射编码给转换回去。这里不需要具体转换，但是需要计算所有合格的转换数量。

　　先看一个简单的示例，假设有字符串"236"，我们如果从头往后去看的话，首先对于第一个数字2它有１中解码方式，对于前两个字符23来说，它有两种解码方式，可以分别解码成2, 3或者23，它们对应的字符分别为BC或者W。但是对于包含整个的字符串236来说，从字符6的位置来看，它本身可以有一个解码，但是看它前面的那个元素则是36，不能解码。所以它整个的解码方式应该就相当于23的所有解码个数。也就是2。

　　从前面的这个示例讨论可以看到，对于给定的字符，假定它当前索引位置为i，如果它这个位置是一个在编码表里的字符，也就是它在1到9之间，那么它的解码方式数量是取决于到它前面那个元素为止的这个串的所有解码方式。但是因为前面的编码里有包含到两位数的数字，所以我们还有一种情况要看，就是它和它前面的那个字符构成的串是否在10到26之间，如果是的话，它的编码方式还包含到i - 2这个位置的所有方式。

　　所以，按照上述的讨论，我们可以得到一个如下的递归推导方式：

        if(s[i]) is valid,  count[i] = count[i - 1];

        if(s[i - 1, i]) is valid, count[i] += count[i - 1];

　　从实现的角度来看，前面判断s[i]是否合法则需要判断s.charAt(i) != '0'

       而判断s[i - 1, i]是否合法，则需要看两个条件，一个是s[i - 1]这个位置的字符不能是'0'而且s[i - 1, i]必须小于等于26。

　　按照这个思路，我们可以得到如下的一个实现：

public class Solution {
    public int numDecodings(String s) {
        if(s.length() == 0) return 0;
        int n = s.length();
        int[] counts = new int[n + 1];
        counts[0] = 1;
        counts[1] = s.charAt(0) != '0' ? 1 : 0;
        for(int i = 2; i <= n; i++) {
            if(s.charAt(i - 1) != '0') counts[i] = counts[i - 1];
            if(s.charAt(i - 2) == '0') continue;
            counts[i] += (Integer.parseInt(s.substring(i - 2, i)) <= 26) ? counts[i - 2] : 0;
        }
        return counts[n];
    }
}

 　　这里是利用了前面的递归关系来构造一个动态规划的实现。代码里的判断因为是从头开始，要考虑判断的逻辑稍微有点复杂。

　　实际上，如果我们从字符串的末尾到开头来，可以使得代码的逻辑更加简练，因为我们每次碰到当前字符如果是'0'的话，就不需要考虑了，直接跳过去就可以了。按照这种思路改进后的代码如下：

 

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] memo = new int[n + 1];
        memo[n] = 1;
        memo[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i, i + 2)) <= 26) ? memo[i + 1] + memo[i + 2] : memo[i + 1];
        }
        return memo[0];
    }
}