字符串排列时的递归问题

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='') => {

  const idx = prefix.length

  if (idx===str.length)

    return [prefix]

  const lower = str[idx].toLowerCase()

  const upper = str[idx].toUpperCase()

  return [...permute(str, prefix + lower), ...permute(str, prefix + upper)]

}

console.log(permute('abc'))

Answer 2

这是一个带有 flatMap 的：

function f(str){

  return str ? f(str.slice(1)).flatMap(sfx =>

    [str[0].toLowerCase() + sfx, str[0].toUpperCase() + sfx]) : [""]

}

console.log(JSON.stringify(f("abc")))

Answer 3

您可以采用递归函数，该函数采用最后访问的索引的收集字母，并检查收集的字母字符串是否与给定字符串的长度相同。然后将字符串推送到结果集。

关键是递归调用一个小写字母和一个大写字母。

function capitalPermutations(word) {

    function iter(temp = '') {

        if (temp.length === word.length) {

            result.push(temp);

            return;

        }

        iter(temp + word[temp.length].toLowerCase());

        iter(temp + word[temp.length].toUpperCase());

    }

    var result = [];

    iter();

    return result;

}

console.log(capitalPermutations('abc'));

与迭代方法相同

function capitalPermutations(word) {

    var result = [''],

        temp,

        i, j, upper, lower;

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

        temp = result;

        result = [];

        lower = word[i].toLowerCase();

        upper = word[i].toUpperCase();

        for (j = 0; j < temp.length; j++) {

            result.push(temp[j] + lower, temp[j] + upper);

        }

    }

    return result;

}

console.log(capitalPermutations('abc'));