回答答案 - 解码方式

这是一个非常有趣的问题.首先,我将展示如何解决这个问题.我们将看到使用递归时并不复杂,并且可以使用动态编程解决问题.我们将生成一个通用解决方案,不对26每个代码点的上限进行硬编码.

在便笺上的术语:我将使用术语代码点(CP)不是在Unicode的意义,而是指代码号码中的一个1,虽然26.每个代码点表示为可变数量的字符.我还将使用术语编码文本(ET)和明文(CT)的明显含义.在谈论序列或数组时,第一个元素称为头部.剩下的元素是尾巴.

理论前奏

EC ""有一个解码:CT "".

EC "3"可以被解构为'3' + "",并且具有一个解码.

EC "23"可以被解构为'2' + "3"或'23' + "".每个尾部都有一个解码,因此整个EC有两个解码.

EC "123"可以被解构为'1' + "23"或'12' + "3".尾巴分别有两个和一个解码.整个EC有三个解码.解构'123' + ""是无效的,因为123 > 26,我们的上限.

...等等任何长度的EC.

因此,给定一个字符串"123",我们可以通过在开头找到所有有效的CP,并总结每个尾部的解码数量来获得解码的数量.

最困难的部分是寻找有效的头脑.我们可以通过查看上限的字符串表示来获得头部的最大长度.在我们的例子中,头部最长可达两个字符.但并非所有适当长度的头都是有效的,因为它们也必须? 26如此.

朴素的递归实现

现在我们已经完成了一个简单(但工作)递归实现的所有必要工作:

static final int upperLimit  = 26;
static final int maxHeadSize = ("" + upperLimit).length();

static int numDecodings(String encodedText) {
    // check base case for the recursion
    if (encodedText.length() == 0) {
        return 1;
    }

    // sum all tails
    int sum = 0;
    for (int headSize = 1; headSize <= maxHeadSize && headSize <= encodedText.length(); headSize++) {
        String head = encodedText.substring(0, headSize);
        String tail = encodedText.substring(headSize);
        if (Integer.parseInt(head) > upperLimit) {
            break;
        }
        sum += numDecodings(tail);
    }

    return sum;
}

缓存递归实现

显然这不是很有效,因为(对于更长的ET),将对多次相同的尾部进行分析.此外,我们创建了许多临时字符串,但我们现在就让它成为现实.我们可以轻松做的一件事就是记住特定尾部的解码次数.为此,我们使用与输入字符串长度相同的数组:

static final int upperLimit  = 26;
static final int maxHeadSize = ("" + upperLimit).length();

static int numDecodings(String encodedText) {
    return numDecodings(encodedText, new Integer[1 + encodedText.length()]);
}

static int numDecodings(String encodedText, Integer[] cache) {
    // check base case for the recursion
    if (encodedText.length() == 0) {
        return 1;
    }

    // check if this tail is already known in the cache
    if (cache[encodedText.length()] != null) {
        return cache[encodedText.length()];
    }

    // cache miss -- sum all tails
    int sum = 0;
    for (int headSize = 1; headSize <= maxHeadSize && headSize <= encodedText.length(); headSize++) {
        String head = encodedText.substring(0, headSize);
        String tail = encodedText.substring(headSize);
        if (Integer.parseInt(head) > upperLimit) {
            break;
        }
        sum += numDecodings(tail, cache);  // pass the cache through
    }

    // update the cache
    cache[encodedText.length()] = sum;
    return sum;
}

请注意,我们使用的是Integer[],而不是int[].这样,我们可以使用测试来检查不存在的条目null.这个解决方案不仅正确,而且速度也非常快 - 天真的递归以O(解码次数)运行,而memoized版本以O(字符串长度)时间运行.

迈向DP解决方案

当你在头脑中运行上面的代码时,你会注意到第一次调用整个字符串会有一个缓存未命中,然后计算第一个尾部的解码次数,每次都会错过缓存.我们可以通过首先从输入结束开始评估尾部来避免这种情况.因为在整个字符串之前已经评估了所有尾部,所以我们可以删除对缓存未命中的检查.现在我们也没有任何递归的理由,因为之前的所有结果都已经在缓存中.

static final int upperLimit  = 26;
static final int maxHeadSize = ("" + upperLimit).length();

static int numDecodings(String encodedText) {
    int[] cache = new int[encodedText.length() + 1];

    // base case: the empty string at encodedText.length() is 1:
    cache[encodedText.length()] = 1;

    for (int position = encodedText.length() - 1; position >= 0; position--) {
        // sum directly into the cache
        for (int headSize = 1; headSize <= maxHeadSize && headSize + position <= encodedText.length(); headSize++) {
            String head = encodedText.substring(position, position + headSize);
            if (Integer.parseInt(head) > upperLimit) {
                break;
            }
            cache[position] += cache[position + headSize];
        }
    }

    return cache[0];
}

通过注意我们只查询maxHeadSize缓存中的最后一个元素,可以进一步优化该算法.因此,我们可以使用固定大小的队列而不是数组.那时,我们将拥有一个在*O(输入长度​​)时间和O(maxHeadSize)空间中运行的动态编程解决方案.

专业化 upperLimit = 26

上面的算法尽可能保持一般,但我们可以针对特定的方法手动专门化它upperLimit.这可能很有用,因为它允许我们进行各种优化.然而,这引入了"魔术数字",使代码难以维护.因此,应该在非关键软件中避免这种手动专业化(并且上述算法已经尽可能快).

static int numDecodings(String encodedText) {
    // initialize the cache
    int[] cache = {1, 0, 0};

    for (int position = encodedText.length() - 1; position >= 0; position--) {
        // rotate the cache
        cache[2] = cache[1];
        cache[1] = cache[0];
        cache[0] = 0;

        // headSize == 1
        if (position + 0 < encodedText.length()) {
            char c = encodedText.charAt(position + 0);

            // 1 .. 9
            if ('1' <= c && c <= '9') {
                cache[0] += cache[1];
            }
        }

        // headSize == 2
        if (position + 1 < encodedText.length()) {
            char c1 = encodedText.charAt(position + 0);
            char c2 = encodedText.charAt(position + 1);

            // 10 .. 19
            if ('1' == c1) {
                cache[0] += cache[2];
            }
            // 20 .. 26
            else if ('2' == c1 && '0' <= c2 && c2 <= '6') {
                cache[0] += cache[2];
            }
        }
    }

    return cache[0];
}

与您的代码比较

代码表面上相似.但是,您对字符的解析更复杂.您已经引入了一个used变量,如果设置,它将减少解码计数,以便考虑双字符CP.这是错的,但我不确定为什么.主要问题是你几乎每一步都要加倍计数.正如我们所看到的,先前的计数被添加,并且可能非常不同.

这表明您在没有适当准备的情况下编写了代码.你可以编写多种软件而不必过多考虑,但在设计算法时你不能没有仔细分析.对我来说,在纸上设计算法通常很有帮助,并绘制每个步骤的图表(沿着这个答案的"理论前奏").当您过多地考虑要实现的语言时,这一点尤其有用,而对于可能错误的假设则太少.

我建议您阅读"感应证明"以了解如何编写正确的递归算法.一旦有了递归解决方案,就可以随时将其转换为迭代版本.

由于我自己也在努力解决这个问题,这是我的解决方案和推理.可能我会大部分重复amon所写的内容,但也许有人会觉得它很有帮助.它也是c#而不是java.

假设我们输入"12131"并希望获得所有可能的解码字符串.直接递归解决方案将从左到右迭代,获得有效的1和2位数头,并为尾部递归调用函数.

我们可以使用树来可视化它:

有5个叶子,这是所有可能的解码字符串的数量.还有3个空叶,因为31号不能解码成字母,所以这些叶子无效.

算法可能如下所示:

public IList<string> Decode(string s)
{
    var result = new List<string>();

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                result.Add(this.ToASCII(s));
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                result.Add(this.ToASCII(s.Substring(0, 1)) + this.ToASCII(s.Substring(1, 1)));
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                result.Add(this.ToASCII(s));
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
            {
                var tails = this.Decode(s.Substring(i));
                foreach (var tail in tails)
                    result.Add(this.ToASCII(head) + tail);
            }
        }
    }

    return result;
}

public string ToASCII(string str)
{
    int number = int.Parse(str);
    int asciiChar = number + 65 - 1; // A in ASCII = 65
    return ((char)asciiChar).ToString();
}

我们必须处理从0开始的数字("0","03"等),并且大于26.

因为在这个问题中我们只需要计算解码方式,而不是实际的字符串,我们可以简化这段代码:

public int DecodeCount(string s)
{
    int count = 0;

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                count++;
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                count++;
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                count++;
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
                count += this.DecodeCount(s.Substring(i));
        }
    }

    return count;
}

该算法的问题在于我们多次计算相同输入字符串的结果.例如,有3个以31结尾的节点:ABA31,AU31,LA31.还有2个节点以131结尾:AB131,L131.我们知道如果节点以31结尾,它只有一个子节点,因为31只能以一种方式解码到CA. 同样,我们知道如果字符串以131结尾,则它有2个子节点,因为131可以解码为ACA或LA.因此,我们可以将其缓存在map中,而不是重新计算它,其中key是string(例如:"131"),value是解码方式的数量:

public int DecodeCountCached(string s, Dictionary<string, int> cache)
{
    if (cache.ContainsKey(s))
        return cache[s];

    int count = 0;

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                count++;
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                count++;
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                count++;
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (head[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
                count += this.DecodeCountCached(s.Substring(i), cache);
        }
    }

    cache[s] = count;
    return count;
}

我们可以进一步完善这一点.我们可以使用length来代替使用字符串作为键,因为缓存的内容始终是输入字符串的尾部.所以不是缓存字符串:"1","31","131","2131","12131"我们可以缓存尾部长度:1,2,3,4,5:

public int DecodeCountDPTopDown(string s, Dictionary<int, int> cache)
{
    if (cache.ContainsKey(s.Length))
        return cache[s.Length];

    int count = 0;

    if (s.Length <= 2)
    {
        if (s.Length == 1)
        {
            if (s[0] != '0')
                count++;
        }
        else if (s.Length == 2)
        {
            if (s[0] != '0' && s[1] != '0')
                count++;
            if (s[0] != '0' && int.Parse(s) > 0 && int.Parse(s) <= 26)
                count++;
        }
    }
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            string head = s.Substring(0, i);
            if (s[0] != '0' && int.Parse(head) > 0 && int.Parse(head) <= 26)
                count += this.DecodeCountDPTopDown(s.Substring(i), cache);
        }
    }

    cache[s.Length] = count;
    return count;
}

这是递归的自上而下的动态编程方法.我们从开始开始,然后递归计算尾部的解决方案,并记住这些结果以供进一步使用.

我们可以将其转换为自下而上的迭代DP解决方案.我们从最后开始并缓存瓷砖的结果,就像之前的解决方案一样.我们可以使用数组而不是map,因为键是整数:

public int DecodeCountBottomUp(string s)
{
    int[] chache = new int[s.Length + 1];
    chache[0] = 0; // for empty string;

    for (int i = 1; i <= s.Length; ++i)
    {
        string tail = s.Substring(s.Length - i, i);

        if (tail.Length == 1)
        {
            if (tail[0] != '0')
                chache[i]++;
        }
        else if (tail.Length == 2)
        {
            if (tail[0] != '0' && tail[1] != '0')
                chache[i]++;
            if (tail[0] != '0' && int.Parse(tail) > 0 && int.Parse(tail) <= 26)
                chache[i]++;
        }
        else
        {
            if (tail[0] != '0')
                chache[i] += chache[i - 1];

            if (tail[0] != '0' && int.Parse(tail.Substring(0, 2)) > 0 && int.Parse(tail.Substring(0, 2)) <= 26)
                chache[i] += chache[i - 2];
        }
    }

    return chache.Last();
}

有些人甚至进一步简化它,用值1初始化cache [0],这样就可以摆脱tail.Length == 1和tail.Length == 2的条件.对我来说这是不直观的技巧,因为很明显,对于空字符串,有0个解码方式不是1,所以在这种情况下必须添加附加条件来处理空输入:

public int DecodeCountBottomUp2(string s)
{
    if (s.Length == 0)
        return 0;

    int[] chache = new int[s.Length + 1];
    chache[0] = 1;
    chache[1] = s.Last() != '0' ? 1 : 0;

    for (int i = 2; i <= s.Length; ++i)
    {
        string tail = s.Substring(s.Length - i, i);

        if (tail[0] != '0')
            chache[i] += chache[i - 1];

        if (tail[0] != '0' && int.Parse(tail.Substring(0, 2)) > 0 && int.Parse(tail.Substring(0, 2)) <= 26)
            chache[i] += chache[i - 2];
    }

    return chache.Last();
}

这是我解决问题的代码.我使用DP,我认为很清楚.

用Java编写

public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            int n = s.length();
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = s.charAt(0) != '0' ? 1 : 0;

            for(int i = 2; i <= n; i++){
                int first = Integer.valueOf(s.substring(i-1,i));
                int second = Integer.valueOf(s.substring(i-2,i));
                if(first >= 1 && first <= 9){
                    dp[i] += dp[i-1];
                }
                if(second >= 10 && second <= 26){
                    dp[i] += dp[i-2];
                }

            }
            return dp[n];

        }

}

所以这里有一些更简单的方法来解决你的问题.这非常接近于计算Fibonacci,不同之处在于每个较小尺寸的子问题都有条件检查.空间复杂度为O(1),时间为O(n)

代码是用C++编写的.

   int numDecodings(string s)
   {
    if( s.length() == 0 ) return 0;


    int j  = 0;
    int p1 = (s[j] != '0' ? 1 : 0);         // one step prev form j=1
    int p2 = 1;                             // two step prev from j=1, empty
    int p = p1;

    for( int j = 1; j < s.length(); j++ )
    {
        p = 0;

        if( s[j] != '0' ) 
            p += p1;    


        if( isValidTwo(s, j-1, j) )
            p += p2;

        if( p==0 )                  // no further decoding necessary, 
            break;                  // as the prefix 0--j is has no possible decoding.

        p2 = p1;                    // update prev for next j+1;
        p1 = p;

    }

    return p;
    }

    bool isValidTwo(string &s, int i, int j)
    {
        int val= 10*(s[i]-'0')+s[j]-'0';

        if ( val <= 9 ) 
        return false;

        if ( val > 26 ) 
        return false;

        return true;

    }