字符串排列时的递归问题

Question

我正在尝试生成字符串的所有大写排列。

例如：

capitalPermutations(word) - 给定一串字母，返回该单词的所有小写和大写字母的可能组合。

示例：'abc'

输出： ['abc' 'Abc' 'aBc' 'ABC' 'abC' 'AbC' 'aBC' 'ABC']

以迭代和递归方式实现这一点。

这是我的尝试：

function capitalPermutations(word) {

  const res = new Set();

  

  // Push the actual word first.

  res.add(word);

  

  helper(word, res, '');

  

  return res;

  

  function helper(word, res, str='') {

    

    if(str.length === word.length) return;

    

    const len = word.length;

    res.add(word);

    

    // Capitalization

    for(let i=0; i< word.length; i++) {

      const substr = word.substring(0, i+1); // a, ab, abc

      str += substr; // str === "ABC" | len = 3

      const upper = str.toUpperCase(); // A, AB, ABC

      const remaining = `${upper}${word.substring(i, len)}`; // Abc , ABc, 

      helper(remaining, res, str);

    }

  }

}

var testWord1 = "abc"

console.log(capitalPermutations(testWord1))

问题： 它将进入无限递归。即使我有一个破坏条件。如果有人可以纠正我出错的地方，我将不胜感激。

Answer 1

像二叉树一样遍历字符串const permute = (str, prefix='') => {&nbsp; const idx = prefix.length&nbsp; if (idx===str.length)&nbsp; &nbsp; return [prefix]&nbsp; const lower = str[idx].toLowerCase()&nbsp; const upper = str[idx].toUpperCase()&nbsp; return [...permute(str, prefix + lower), ...permute(str, prefix + upper)]}console.log(permute('abc'))

Answer 2

这是一个带有 flatMap 的：function f(str){&nbsp; return str ? f(str.slice(1)).flatMap(sfx =>&nbsp; &nbsp; [str[0].toLowerCase() + sfx, str[0].toUpperCase() + sfx]) : [""]}console.log(JSON.stringify(f("abc")))

Answer 3

您可以采用递归函数，该函数采用最后访问的索引的收集字母，并检查收集的字母字符串是否与给定字符串的长度相同。然后将字符串推送到结果集。关键是递归调用一个小写字母和一个大写字母。function capitalPermutations(word) {&nbsp; &nbsp; function iter(temp = '') {&nbsp; &nbsp; &nbsp; &nbsp; if (temp.length === word.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push(temp);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; iter(temp + word[temp.length].toLowerCase());&nbsp; &nbsp; &nbsp; &nbsp; iter(temp + word[temp.length].toUpperCase());&nbsp; &nbsp; }&nbsp; &nbsp; var result = [];&nbsp; &nbsp; iter();&nbsp; &nbsp; return result;}console.log(capitalPermutations('abc'));与迭代方法相同function capitalPermutations(word) {&nbsp; &nbsp; var result = [''],&nbsp; &nbsp; &nbsp; &nbsp; temp,&nbsp; &nbsp; &nbsp; &nbsp; i, j, upper, lower;&nbsp; &nbsp; for (i = 0; i < word.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; temp = result;&nbsp; &nbsp; &nbsp; &nbsp; result = [];&nbsp; &nbsp; &nbsp; &nbsp; lower = word[i].toLowerCase();&nbsp; &nbsp; &nbsp; &nbsp; upper = word[i].toUpperCase();&nbsp; &nbsp; &nbsp; &nbsp; for (j = 0; j < temp.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push(temp[j] + lower, temp[j] + upper);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return result;}console.log(capitalPermutations('abc'));