javascript - 字符串排列时的递归问题

Question

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

例如:

capitalPermutations(word) - Given a string of letters, return all the possible combinations of lower and uppercase letters of that word.

Example: 'abc'

Ouput: ['abc' 'Abc' 'aBc' 'ABc' 'abC' 'AbC' 'aBC' 'ABC']

Implement this in both iterative and recursive way.

这是我的尝试:

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