主页 / 问题 / 1432119
Accepted
MrYogurt
Asked:2022-07-22 20:52:34 +0000 UTC2022-07-22 20:52:34 +0000 UTC

如何简化所有组合的迭代

  • 772

有一个对象：

const letters = {
    1: ['a', 'b', 'c'],
    2: ['d', 'e', 'f'],
    3: ['g', 'h', 'i'],
    4: ['j', 'k', 'l'],
    5: ['m', 'n', 'o'],
    6: ['p', 'q', 'r'],
    7: ['s', 't', 'u'],
    8: ['v', 'w', 'x'],
    9: ['y', 'z']
}

有必要编写一个函数来返回字符串传递的数字的所有可能组合。我是这样做的：

const func = (str) => {
  if (str.length === 0) return []

  const strArr = str.split('')
  const result = []
  
  const arrays = strArr.map(item => letters[item])

  if (strArr.length === 1) return arrays[0]
  
  for (let letterIndex = 0; letterIndex < arrays[0].length; letterIndex++) {
    const word = arrays[0][letterIndex]

    for (let arrayIndex = 1; arrayIndex < arrays.length; arrayIndex++) {
      
      for (let letterArrayIndex = 0; letterArrayIndex < arrays[arrayIndex].length; letterArrayIndex++) {
        const secondWord = word + arrays[arrayIndex][letterArrayIndex]
        
        if (arrays.length > 2) {
          for (let restArrays = arrayIndex + 1; restArrays < arrays.length; restArrays++) {
            for (let i = 0; i < arrays[restArrays].length; i++) {
              result.push(secondWord + arrays[restArrays][i])
            }
          }
        } else {
          result.push(secondWord)
        }
      }
    }
  }
  
  return result
}

预期结果：

func('') => []
func('2') => ['d', 'e', 'f']
func('23') => ["dg","dh","di","eg","eh","ei","fg","fh","fi"]

但显然它看起来很丑。我觉得这可以通过递归以某种方式很好地解决，但我不知道该怎么做。

javascript алгоритм

2 个回答

  1. func('') => []我将要求更改为func('') => ['']. 这样更合乎逻辑。

         const letters = {
        1: ['a', 'b', 'c'],
        2: ['d', 'e', 'f'],
        3: ['g', 'h', 'i'],
        4: ['j', 'k', 'l'],
        5: ['m', 'n', 'o'],
        6: ['p', 'q', 'r'],
        7: ['s', 't', 'u'],
        8: ['v', 'w', 'x'],
        9: ['y', 'z']
    }
    
    const func = digits => {
        if (digits.length === 0) {
            return [''];
        }
        const result = [];
        const strs = func(digits.substring(1));
        for (const c of letters[+digits[0]]) {
            for (const s of strs) {
                result.push(c + s);
            }
        }
        return result;
    };
    
    console.log(func('23'));

    • 2
  2. Best Answer

    没有递归的变体：

    const letters = {
    1: ['a', 'b', 'c'],
    2: ['d', 'e', 'f'],
    3: ['g', 'h', 'i'],
    4: ['j', 'k', 'l'],
    5: ['m', 'n', 'o'],
    6: ['p', 'q', 'r'],
    7: ['s', 't', 'u'],
    8: ['v', 'w', 'x'],
    9: ['y', 'z']
};

const getAllCombinationsOfTwoArr = (arr1, arr2) => {
  const result = [];
  
  for (const str1 of arr1) {
    for (const str2 of arr2) {
      result.push(str1 + str2);
    }
  }
  
  return result;
}

const getAllCombinations = (str, alphabet) => {
  if (str.length === 0) return [];
  
  const rowsNum = str.split('');
  let result = [''];
  
  for (const rowNum of rowsNum) {
    result = getAllCombinationsOfTwoArr(result, alphabet[rowNum]);
  }
  
  return result;
}

console.log(getAllCombinations('', letters));
console.log(getAllCombinations('1', letters));
console.log(getAllCombinations('12', letters));
console.log(getAllCombinations('123', letters));

    • 2

相关问题