javascript - 为什么我的 DP 解码数字和字母解决方案不能适用于所有测试用例？

Question

上下文
这个问题是dailycodingproblem和leetcode问的

/* 给定映射 a = 1、b = 2、... z = 26 和编码消息，计算可以解码的方式数量。

例如，消息“111”将给出 3，因为它可以被解码为“aaa”、“ka”和“ak”。

您可以假设消息是可解码的。例如，不允许使用“001”。 */

var AlphabetCode = function(){};
AlphabetCode.prototype.decode = function(message) {
    //dp is optimal substructure, account for zero length string such as dp[0]
    let dp = Array(1+message.length).fill(0);
    //string is of length zero
    dp[0] = 0; // no ways to decode empty (tried toggling between 0 and 1)  
    //string is of length one
    dp[1] = parseInt(message[0]) == 0 ? 0 : 1; // there is no alphabet code for 0, 'a' starts at 1 

    //string is of length two or greater
    // go up to string length inclusive because index 0 is reserved for zero string
    for (let i = 2; i <= message.length; i++){
        let singleDigit = message.substring(i-1, i);
        let doubleDigit = message.substring(i-2, i);
        //console.log(singleDigit + ' ' + doubleDigit);
        //console.log(singleDigit[0]);
        if (1 <= parseInt(singleDigit) <= 9){
            dp[i] += dp[i-1];
            //console.log(dp[i]);
        }
        //console.log(doubleDigit[0]);
        if (doubleDigit[0] !='0' && 10 <= parseInt(doubleDigit) <= 26){
            //console.log('double valid');
            dp[i] += dp[i-2];
        }
    }
    // filled out the dp array and returning the accumulation of all subproblems
    return dp[message.length];
};
combinations = new AlphabetCode();
console.log('Number of ways to decode 10 are: (expect 1) ' + combinations.decode('10'));
console.log('Number of ways to decode 12 are: (expect 2) ' + combinations.decode('12'));
console.log('Number of ways to decode 226 are: (expect 3) ' + combinations.decode('226'));
console.log('Number of ways to decode 27 are: (expect 1) ' + combinations.decode('27'));

输出

Number of ways to decode 10 are: (expect 1) 1 
Number of ways to decode 12 are: (expect 2) 1
Number of ways to decode 226 are: (expect 3) 2
Number of ways to decode 27 are: (expect 1) 1

dp 是最优子结构。尝试将 dp[0] 更改为 0 或 1 以通过所有测试用例，但输出并不总是等于预期数字。

Answer 1

两个问题:

• 正如您已经尝试过的那样，但 dp[0] 应该为 1，因为实际上空字符串是空消息的有效编码。所以它很重要。

• 您无法在 JavaScript 中进行 Python 风格的双重比较，因此这两个条件均无效:

  if (1 <= parseInt(singleDigit) <= 9)
  if (doubleDigit[0] !='0' && 10 <= parseInt(doubleDigit) <= 26)
  

  将它们更改为；

  if (1 <= parseInt(singleDigit))
  if (doubleDigit[0] !='0' && parseInt(doubleDigit) <= 26)
  

  删除的“条件”已经保证为真:当您已经验证第一位数字不是零时，单个数字不能大于 9，并且双位数至少为 10。

代码的一些注释

创建构造函数是多余的，因为您不维护该“类”的实例中的状态。相反，创建一个以函数作为成员的对象。

此外，您不需要 dp 为每个可能的字符串长度都有一个条目，因为您只需要“最后”两个结果来计算下一个结果，因此您只需两个结果即可值。

最后，使用三元运算符和一元加号(用于转换为数字)，您可以非常简洁地计算下一个计数:

const combinations = {
    decode(message) {
        // Only need memory of past two results (for string length - 1, and - 2)
        let dp = [1, 1];
        // No need to reject a starting zero, as the challenge says only valid input is given.
        for (let i = 2; i <= message.length; i++){
            let singleDigit = +message[i-1];
            let doubleDigit = +message.substring(i-2, i);
            dp = [
                dp[1], 
                (1 <= singleDigit) * dp[1]
                    + (10 <= doubleDigit && doubleDigit <= 26) * dp[0]
            ];
        }
        return dp[1];
    }
};

console.log('Number of ways to decode 10 are: (expect 1) ' + combinations.decode('10'));
console.log('Number of ways to decode 12 are: (expect 2) ' + combinations.decode('12'));
console.log('Number of ways to decode 226 are: (expect 3) ' + combinations.decode('226'));
console.log('Number of ways to decode 27 are: (expect 1) ' + combinations.decode('27'));