CODEWITHSUNDEEP
javascriptstringalgorithm
barakbd
barakbd

Reputation: 1102

Recursion with substring/slice in javascript

Writing a recursion algorithm to get anagrams of a string. Expected output for string abc is ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

However, what I get is [ 'abc', 'acb', 'ba', 'cab', 'cba' ].

I know where the issue is: When the recursion goes back to level 0 (meaning str==='abc' and i==1), substring works (exracts 'a'), but slice does not(does not extract c).

function anagramPermutationMemo(str, memo, resultsArr, level) {
    if (!memo) {
        memo = '';
        resultsArr = [];
        level = 0;
    }
    console.log('str -', str);
    console.log('memo -', memo, '\n');

    if (str.length === 0) {
        resultsArr.push(memo);
        return;
    }
    for (var i in str) {
        console.log('level', level);
        console.log('str', str);
        console.log('i -', i, str[i]);
        console.log('substring', str.substring(0, i));
        console.log('slice', str.slice(i + 1));
        var newStr = str.substring(0, i).concat(str.slice(i + 1));
        console.log('newStr - ', newStr, '\n');
        anagramPermutationMemo(newStr, memo + str[i], resultsArr, level + 1);
    }
    level -= 1;
    console.log('backtrack', level,'\n');

    return resultsArr;
};

Upvotes: 2

Views: 1257

Answers (2)

guest271314
guest271314

Reputation: 1

I know where the issue is

The issue is for..in loop.

Explanation:

variable of for..in loop is a String, not a Number. Within bracket notation 

str[i]

expected result is returned, as property of object is a string, e.g., str["0"]; Number can also be used to get property of object within bracket notation str[0].

String.prototype.slice() calls ToInteger on parameters, though does not return expected result without casting string to number using sign

ToInteger

The abstract operation ToInteger converts its argument to an integral numeric value. This abstract operation functions as follows:

  1. Let number be the result of calling ToNumber on the input argument.
  2. If number is NaN, return +0.
  3. If number is +0, −0, +∞, or −∞, return number.
  4. Return the result of computing sign(number) × floor(abs(number)).

String.prototype.substring() expects Number as parameter.

If either argument is NaN or negative, it is replaced with zero; if either argument is larger than the length of the String, it is replaced with the length of the String.

Solution, substitute for loop for for..in loop

function anagramPermutationMemo(str, memo, resultsArr, level) {
  if (!memo) {
    memo = '';
    resultsArr = [];
    level = 0;
  }
  console.log('str -', str);
  console.log('memo -', memo, '\n');

  if (str.length === 0) {
    resultsArr.push(memo);
    return;
  }
  for (var i = 0; i < str.length; i++) {
    console.log('level', level);
    console.log('str', str);
    console.log('i -', i, str[i]);
    console.log('substring', str.substring(0, i));
    console.log('slice', str.slice(i + 1));
    var newStr = str.substring(0, i).concat(str.slice(i + 1));
    console.log('newStr - ', newStr, '\n');
    anagramPermutationMemo(newStr, memo + str[i], resultsArr, level + 1);
  }
  level -= 1;
  console.log('backtrack', level, '\n');

  return resultsArr;
};

var p = anagramPermutationMemo("abc");

console.log(p);

Solution:

Cast i parameter to Number using + operator at calls to .substring(), .slice() when using for..in loop, where parameters of methods are expecting Number.

function anagramPermutationMemo(str, memo, resultsArr, level) {
  if (!memo) {
    memo = '';
    resultsArr = [];
    level = 0;
  }

  if (str.length === 0) {

    resultsArr.push(memo);
    return;
  }
  for (var i in str) {
    
    var newStr = str.substring(0, +i).concat(str.slice(+i + 1));
    var _newStr = str.substring(0, i).concat(str.slice(i + 1));
    
    console.log(`newStr with string as parameter:${_newStr}`);
    console.log(`newStr with number as parameter:${newStr}`);
    console.log(`i:${str.substring(0, i)}, ${str.slice(i + 1)}`);
    console.log(`+i:${str.substring(0, +i)}, ${str.slice(+i + 1)}`)

    anagramPermutationMemo(newStr, memo + str[i], resultsArr, level + 1);

  }
  level -= 1;

  return resultsArr;
};

Object.defineProperty(String, "abc", {
  value:123,
  enumerable:true
})

var p = anagramPermutationMemo("abc");

console.log(p);

Upvotes: 0

Bergi
Bergi

Reputation: 665122

It would help if you'd also log the value of i+1 (which you're passing to slice). The problem with your for…in enumeration is that it enumerates properties, which are strings. Your i will be "0", "1" and "2" (and possibly other things if String.prototype was extended with enumerable methods).

When you add 1 to that, it's doing string concatenation, and you'll end up with "01", "11" and "21" instead of the desired numbers. Given that slice casts its arguments to numbers, "01" actually works as desired, but the others will lead to indices after the end of the string, so you end up with omitting those parts entirely:

anagramPermutationMemo("abc".substring(0, "1")+"abc".slice("11"), ""+"abc"["1"], […], 0+1);
//                                                         ^^^^ should be 2
anagramPermutationMemo("a",                                       "b",           […], 1);
//                      ^ should be "ac"

To fix the issue, just use a standard for (var i=0; i<str.length; i++) loop.

Upvotes: 1

Related Questions