javascript - 一个数字可以有多少种不同的解码方式

Question

我很困惑，不知道该怎么办。下面的代码是我在思考解决方案时记下的内容。

这是带有示例的问题:

包含 A-Z 字母的消息 使用以下映射将其编码为数字:

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

给定一个仅包含数字的非空字符串，确定解码它的方法总数。

示例1:

输入:“12” 输出:2 解释:可以解码为“AB”(1 2)或“L”(12)。 示例2: 输入:“226” 输出:3 说明:可以解码为“BZ”(2 26)、“VF”(22 6)或“BBF”(2 2 6)。

const numDecodings = (s) => {
  // const alphabet = 'abcdefghijklmnopqrstuvwxyz'.split('')
  // //write an object with alphabets. The numbers will be keys and the letters will be value

  const alphaObject = {
    1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 
    10: 'j', 11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 
    18: 'r', 19: 's', 20: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z'
  };

  const countObj = {};
  // console.log()

  if (s >= "11") {
    s.split("");
    if (!countObj[alphaObject[s]]) {
      return (countObj[alphaObject[s]] = 1);
    }

    //i return the length because
    //i noticed from the examples that the outputs matched the length.
    //since every digit represents a letter.
    //And every letter is a way to do the problem
  } else if (s <= "10") {
    return 1;
  } else if (s === "0") {
    return 0;
  }
  // else if(s.length >= 4){
  //     //test case 1223
  //     //abbc
  //     //lw
  //     //abw
  //     //lbc
  //     //avc
  //     // return s.length + 2
  //     s.alphaObject

  // }
};
//getting it wrong for testcase 0
console.log(numDecodings("14"));

Answer 1

这可以递归完成:

• 查看字符串长度是否为空，而不是返回 1，因为拆分有效。

• 如果它是一个在第一个位置以“0”开头的字符串，那么这不可能是任何解决方案，因为(仅允许 1-26)=> 返回 false。

• 如果长度为 1，则可能 (1-9) => 返回 1。

• 看看没有第一个字符的字符串是否可以通过递归解决 看看是否有第二种可能的 2 位数字分割方法。
  
  

• 如果字符串长度至少为 2 个字符，并且整数值最大为 26，这可能是一个解决方案，在没有前 2 个字符的情况下继续递归......

• 现在看看两个尝试是否都不为 false => 将两个返回结果相加。

• 如果只有第二个不为 false => 返回此结果。

• 否则返回第一个结果。

function numDecodings(string) {
    if (string.length===0)
        return 1;
    else if (string.charAt(0)==='0')
        return false;
    else if (string.length==1)
        return 1;
        
    let one = numDecodings(string.slice(1));
          
    let test = parseInt(string.substr(0,2));
    if (string.length>=2 && test<=26) {
           let two = numDecodings(string.slice(2));
         if (two!=false && one!=false)
             return one+two;
         else if (two!=false)
             return two;
    }
    return one;
}

console.log(numDecodings ('226')); // 2,2,6 / 22,6 / 2,26 =>3
console.log(numDecodings ('1223')); // 1,2,2,3 / 12,2,3 / 12,23 / 1,22,3 / 1,2,23 => 5
console.log(numDecodings ('1203')); // 1,20,3 => 1