Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am working on a code project that checks if all the characters in str1 can be arranged to form another string (str2). If all the characters in str2 are present in str1 (including any repeated characters in str2, i.e. if str2 has two 'a' characters, str1 must correspondingly have two as well), then the function returns true.

For example, here are some test cases below and the intended return:

str1 = 'rkqodlw'
str2 = 'world'
Expected: true

str1 = 'cedewaraaossoqqyt'
str2 = 'codewars'
Expected: true

str1 = 'katas'
str2 = 'steak'
Expected: false

str1 = 'scriptjava'
str2 = 'javascript'
Expected: true

I have a working code solution, but I'd like to refactor for optimal performance as there are a quite a number of random tests (of unknown length) that the code must test against and my code isn't completing the tests in the recommended timeframe.

function stringscrambling(str1, str2) {
  var arr1 = str1.split('');
  var arr2 = str2.split('');
  var index;
  var l = arr2.length;

  while (l--) {
    index = arr1.indexOf(arr2[l]);
    if (index > -1) {
      arr1.splice(index, 1);
    } else { 
    return false;
    };
  }
  return true;
}

I originally used a basic for loop (with the array length cached as a variable and not in the for statement) as follows:

for (var i = 0, l = arr2.length; i < l ; i++) {
    index = arr1.indexOf(arr2[i]);
    if (index > -1) {
      arr1.splice(index, 1);
    } else { 
      return false;
    };
  }
  return true;
 }

but tried the while-loop in reverse as I read that specific looping would offer a bit better in terms of benchmarked performance. The change in loop offered a negligible performance upgrade.

Are there any other specific tricks I can implement on my code that can speed it up and still retain the original functionality?

share|improve this question

migrated from stackoverflow.com Jan 19 at 20:13

This question came from our site for professional and enthusiast programmers.

    
I think I might be misunderstanding what you're trying to achieve. Do you think you could provide examples of strings that would and would not pass the test? – Robert Ingrum Jan 19 at 19:53
    
Hi Robert, the code passes the tests (i'm privy to a handful of the test cases and they all consist of str1 and str2 strings of less than 60 lowercase alpha characters ONLY) but there is a 6000ms timeout and apparently my code is not completing all the tests in the specified timeframe. – dpg5000 Jan 19 at 19:55
    
This lacks an example like "abcd", "abracadabra", false. – greybeard Jan 19 at 20:51
    
I believe the term is 'anagram'. – Pharap Jan 20 at 10:51
    
Would you mind testing and posting performance comparisons of the various algorithms? – Jack A. Jan 20 at 12:09
up vote 2 down vote accepted

Here's another hash-based algorithm. It compiles the target string (str2) into a hash of characters and counts, then it iterates through the characters in the source string (str1) and decrements the counts in the hash (decompiles). If all of the character counts from the target are consumed, it is a match.

function stringscrambling(target, source) {
  var ntarget = target.length, nsource = source.length;
  if (ntarget <= nsource) {
    // compile the target
    var charhash = {};
    for (var i = 0; i < ntarget; ++i) {
      var c = target[i];
      charhash[c] = (charhash[c] || 0) + 1;
    }

    // decompile the target
    for (var i = 0; i < nsource && ntarget > 0; ++i) {
      var c = source[i];
      if (charhash[c]) {
        --charhash[c];
        --ntarget;
      }
    }
  }
  return ntarget == 0;
}

Here's a fiddle to show it works: https://jsfiddle.net/zwotntg5/

This approach assumes that the performance of accessing characters in a string by index and accessing properties in an object/hash is better than array-based operations.

share|improve this answer
    
why "thestring", "grenastrictichal" equals true? – Nina Scholz Jan 20 at 8:49
    
Because all of the characters in "thestring" can be found in "grenastrictichal". It's the same as the "codewars"-in-"cedewaraaossoqqyt" case in the original question. – Jack A. Jan 20 at 12:08
    
the original question does not included some examples. ty. – Nina Scholz Jan 20 at 12:15

The way to improve your performance is to use a better algorithm, specifically, sort both strings and compare:

function stringscrambling(str1, str2) {
 var sort1 = str1.split('').sort().join('');
 var sort2 = str2.split('').sort().join('');

 return sort1 === sort2;
}
share|improve this answer
1  
Hi Amit! Thanks for the help, however I realized that this might not work for my needs (i.e. str1 may be of larger length than str2, so a strict sort and compare between strings wouldn't return properly for all test cases). I added some test cases above that hopefully sheds more light on what's the requirement for the code. – dpg5000 Jan 19 at 20:23
    
While sorting and comparing isn't quite enough, it's almost there: walk both sort results checking whether for equality. Skip "1" when smaller, return false if end on 1 or greater, true when end on 2. (You may consider the approaches establishing char -> count an application of counting sort.) – greybeard Jan 19 at 20:52
1  
@greybeard - That will work, and would probably be ideal provided the input was fairly short. Sorting takes longer than using a map as in James' solution, so I'd prefer that if the input could get long... – Darrel Hoffman Jan 19 at 21:27

It might be useful to create an object which contains each character and their count in the string.

e.g.

var str1 = "Foobar";
var str2 = "Foobarbaz";

var str1Count = {
  "F": 1,
  "o": 2,
  "b": 1,
  "a": 1,
  "r": 1
}

var str2Count = {
  "F": 1,
  "o": 2,
  "b": 2,
  "a": 2,
  "r": 1,
  "z": 1
}

And then compare the counts to see if one string can compose another.

Consideration: I am assuming there could be 'extra' characters in one of the strings. If each string is equal length and we're just trying to see if we can rearrange one into another, the above suggestion about sorting should work just fine.

To create the suggested object, you could do this:

var letterCount = function(str){
  var letterCount = {};

  str.split('').forEach(function(char){
    letterCount[char] = letterCount[char] === undefined ? 1 : letterCount[char] + 1;
  });

  return letterCount;
}
share|improve this answer
    
I'd go for this solution because it's an O(n) time-complexity algorithm. Run through each string once and count letters, then run through each count and compare. The sorting method may be easier, but it runs in O(n log n), so will take noticeably longer as your input size increases. Of course there's a trade-off in that this adds space complexity instead, but if you limit the input to just the standard ASCII range, it's not all that much memory. – Darrel Hoffman Jan 19 at 21:24
    
Reminds me of Huffman coding. – Pharap Jan 20 at 10:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.