javascript - 将数字转换为字符串并返回所有可能的排列

Question

我正在观看直播mock interview出现了这个问题:

问题指出给定一个数字，例如 12258 。将其转换为字符串，假设每个数字都与字母 1=a, 2=b...z=26 相关联。 。另外，找到该数字的所有可能的翻译。例如:

'1,2,2,5,8' = aabeh
'12,2,5,8 = lbeh
'1,22,5,8' = avbeh ...etc.

我能够获取该数字并将其转换为字符串 aabeh很容易，如以下代码片段所示:

var num = 12258;

var dict = {
  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"
}

function translate(n) {
  n = String(n).split('').map((el, i, arr) => {
    return dict[el]
  }).join('')

  return n;

}

console.log(translate(num));

但是，我正在努力创建一个函数来创建数字的各种排列。

我最初的思考过程是找到 2 位数字 < 26 的所有可能组合。

function translateMult(n) {
    var initArr = String(n).split('');

    var possibleCombo = initArr.map((el,i,arr)=>{
        if(parseInt(arr[i-1] + arr[i]) < 26){
            arr.push(arr[i-1] + arr[i]);
       }
       return arr;
    }); 

    return possibleCombo
}

这会创建 5 个数组，其中包括 [ '1', '2', '2', '5', '8', '12', '22', '25' ] 。我相信我需要检查 initArr 中的每个数字的['1', '2', '2', '5', '8']如果说 1+2 === 12 && < 26返回12 ，但然后删除 1,2 。但我很难弄清楚如何去做。

我也尝试过 for loop因为我认为这可能会扰乱我的思维……

for (var i = 1; i < arr.length; i++) {
  if(parseInt(arr[i-1] + arr[i]) < 26){
    arr.push(arr[i-1] + arr[i]);
  } 
}

但这又给了我一个包含所有可能的数字组合的数组。我显然错过了逻辑的下一步。任何帮助将不胜感激。

Answer 1

这似乎是一个明确的界限dynamic programming问题。概念性的答案是构建一棵树，并用由第一个数字组成的分支对其进行初始化。然后对于每个连续的数字，您:

1. 对每个分支进行 fork ，使得最后一个数字和新数字可以形成新的翻译 ( lastDigit*10 + digit <= 26 )。

2. 将数字附加到每个分支(不包括步骤 1 中的新分支)。

这是一个生成每个翻译的函数:

function translations( number ) {

    // Convert our number into an array of digits
    const digits = number.toString().split( "" ).map( digit => parseInt( digit ) );

    // Initialize our tree with a single sequence of the first digit
    const translations = [[ digits[ 0 ] ]];

    // Loop through remaining digits
    for ( let i = 1; i < digits.length; i ++ ) {

        // Loop through translations; don't include ones we add on this step
        const length = translations.length;
        for ( let n = 0; n < length; n ++ ) {

            // Fork the translation if lastDigit * 10 + currentDigit is within our range
            const sum = translations[ n ][ translations[ n ].length - 1 ] * 10 + digits[ i ];
            if ( sum <= 26 ) translations.push( [ ...translations[ n ].slice( 0, - 1 ), sum ] );

            // Append currentDigit to the translation
            translations[ n ].push( digits[ i ] );

        }

    }

    const values = "abcdefghijklmnopqrstuvwxyz";
    return translations.map( translation => translation.map( key => values[ key - 1 ] ).join( "" ) );

}

如果您只需要计数，您的翻译数组可以是代表每个分支的最后一个值的数字数组。