CODEWITHSUNDEEP
javascriptrecursion
TechnoCorner
TechnoCorner

Reputation: 5155

Issue with recursion while Permutations of a String

I'm trying to generate all capital permutations of a string.

For example:

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.

This is my attempt:

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

Issue: It's going into infinite recursion. Even though I have a breaking condition. Would really appreciate if someone can correct where I'm going wrong.

Upvotes: 2

Views: 146

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Iterative:

function f(str){
  let res = [""]
  for (let c of str)
    res = res.flatMap(pfx =>
      [pfx + c.toUpperCase(), pfx + c.toLowerCase()])
  return res
}

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

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

Here's one with 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")))

Upvotes: 2

Nina Scholz
Nina Scholz

Reputation: 386654

You could take a recursive function which takes the collected letters of the last visited indices and check if the collected letter string has the same length as the given string. Then push the string to the result set.

The key is a double call of the recursion with a lower case letter and an upper case letter.

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

The same with an iterative approach

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

Upvotes: 2

Bill Cheng
Bill Cheng

Reputation: 956

Traverse the string like a binary tree

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

Upvotes: 2

Related Questions