查看答案-解码方式

查看答案-解码方式

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

26

每个代码点的上限进行硬编码。

在便笺上 的术语 ：我将使用术语 代码点
（CP）不是在Unipre的意义，而是指代码号码中的一个

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 enpredText) {    // check base case for the recursion    if (enpredText.length() == 0) {        return 1;    }    // sum all tails    int sum = 0;    for (int headSize = 1; headSize <= maxHeadSize && headSize <= enpredText.length(); headSize++) {        String head = enpredText.substring(0, headSize);        String tail = enpredText.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 enpredText) {    return numDecodings(enpredText, new Integer[1 + enpredText.length()]);}static int numDecodings(String enpredText, Integer[] cache) {    // check base case for the recursion    if (enpredText.length() == 0) {        return 1;    }    // check if this tail is already known in the cache    if (cache[enpredText.length()] != null) {        return cache[enpredText.length()];    }    // cache miss -- sum all tails    int sum = 0;    for (int headSize = 1; headSize <= maxHeadSize && headSize <= enpredText.length(); headSize++) {        String head = enpredText.substring(0, headSize);        String tail = enpredText.substring(headSize);        if (Integer.parseInt(head) > upperLimit) { break;        }        sum += numDecodings(tail, cache);  // pass the cache through    }    // update the cache    cache[enpredText.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 enpredText) {    int[] cache = new int[enpredText.length() + 1];    // base case: the empty string at enpredText.length() is 1:    cache[enpredText.length()] = 1;    for (int position = enpredText.length() - 1; position >= 0; position--) {        // sum directly into the cache        for (int headSize = 1; headSize <= maxHeadSize && headSize + position <= enpredText.length(); headSize++) { String head = enpredText.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 enpredText) {    // initialize the cache    int[] cache = {1, 0, 0};    for (int position = enpredText.length() - 1; position >= 0; position--) {        // rotate the cache        cache[2] = cache[1];        cache[1] = cache[0];        cache[0] = 0;        // headSize == 1        if (position + 0 < enpredText.length()) { char c = enpredText.charAt(position + 0); // 1 .. 9 if ('1' <= c && c <= '9') {     cache[0] += cache[1]; }        }        // headSize == 2        if (position + 1 < enpredText.length()) { char c1 = enpredText.charAt(position + 0); char c2 = enpredText.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。这是错误的，但是我不确定为什么。主要问题是您几乎在每一步都将计数加倍。正如我们所看到的，以前的计数是
相加的 ，可能会有所不同。

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

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