查看答案-解码方式

Question

我正在尝试解决一个问题，这里的问题是 为什么我的解决方案不起作用？ 。这是问题，下面是答案。

问题来自leetcode：http：//oj.leetcode.com/problems/decode-
ways/

使用以下映射将包含来自AZ的字母的消息编码为数字：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定包含数字的已编码消息，请确定对其进行解码的总数。

例如，给出编码消息“ 12”，它可以被解码为“ AB”（1 2）或“ L”（12）。解码“ 12”的方式数为2。

我的解决方案：

我的解决方案的重点是向后退，如果发现拆分，则增加选项数量。拆分是指可以用两种方式解释数字。例如：11可以两种方式解释“ aa”或“ k”。

public class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int decodings = 1;
        boolean used = false; // Signifies that the prev was already use as a decimal
        for (int index = s.length()-1 ; index > 0 ; index--) {
            char curr = s.charAt(index);
            char prev = s.charAt(index-1);
            if (curr == '0') {
                if (prev != '1' && prev != '2') {
                    return 0;
                }
                index--; // Skip prev because it is part of curr
                used = false;
            } else {
                if (prev == '1' || (prev == '2' && curr <= '6')) {
                    decodings = decodings * 2;
                    if (used) {
                        decodings = decodings - 1;
                    }
                    used = true;
                } else {
                    used = false;
                }
            }
        }
        return decodings;
    }
}

失败在以下输入上：

Input:"4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"
Output: 3274568
Expected: 589824

Answer 1

这是一个非常有趣的问题。首先，我将展示如何解决这个问题。我们将看到使用递归时并不会那么复杂，并且可以使用动态编程来解决该问题。我们将提供一种通用解决方案，该解决方案不对26每个代码点的上限进行硬编码。

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

理论前奏

• EC ""具有 一种 解码方式：CT ""。
• "3"可以将EC 分解为'3' + ""，并进行 一次 解码。
• "23"可以将EC 重构为'2' + "3"或'23' + ""。每个尾部都有 一个 解码，因此整个EC都有 两个 解码。
• "123"可以将EC 重构为'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（解码次数） 时间运行，而备忘录版本以 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。这是错误的，但是我不确定为什么。主要问题是您几乎在每一步都将计数加倍。正如我们所看到的，以前的计数是
相加的 ，可能会有所不同。

这表明您没有适当准备就编写了代码。您可以写很多种软件而不必考虑太多，但是在设计算法时必须仔细分析。对我而言，在纸上设计算法并绘制每个步骤的图表（沿该答案的“理论前奏”的路线）通常会很有帮助。当您过多考虑将要实现的语言而对可能的错误假设考虑得太少时，这特别有用。

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