javascript - 一个数字有多少种不同的解码方式
问题描述
我很困惑,我不知道该怎么办。下面的代码是我在考虑解决方案时记下的内容。
这是带有示例的问题:
使用以下映射将包含来自 AZ 的字母的消息编码为数字:
'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"));
解决方案
这可以递归完成:
查看字符串长度是否为空而不是返回 1,因为拆分有效。
如果它是一个在第一个位置以“0”开头的字符串,那么这不可能是任何解决方案,因为(仅允许 1-26)=> 返回 false。
如果它的长度为 1,那么这是可能的 (1-9) => 返回 1。
通过递归查看没有第一个字符的字符串是否是可能的解决方案查看是否有可能使用 2 位数字的第二个拆分方法。
如果字符串至少有 2 个字符长并且整数值最大为 26,这可能是一个解决方案,请在没有前 2 个字符的情况下继续递归。
现在看看是否两个尝试都不为假 => 总结两个返回结果。
如果只有第二个不为假 => 返回此结果。
否则返回第一个结果。
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