How can I compare two shuffled strings?

Question

I have the following two strings:

var str1 = "hello"; var str2 = "ehlol"; 

How can I check whether both strings contain the same characters?

Answer 1

May not be very optimal, but you can simply do

str1.split("").sort().join() == str2.split("").sort().join(); //outputs true 

Another suggested approach in one the comments (for optimization in case string length is quite big)

str1.length===str2.length && str1.split("").sort().join() == str2.split("").sort().join(); //first check the length to quickly rule out in case of obvious non-matches 

Answer 2

One of the recommended ways to do it is using a hash table: count how many times each character appears. Note that this works best if your characters are ASCII.

The complexity of this algorithm is O(M+N+sigma) where M, N are the lengths of the strings and sigma is the number of distinct letters. The complexity of the accepted solution is higher because of the sorting, which is usually done in O(N*logN), but still a good one if your strings are short. If your strings have hundreds of thousands of characters, then this is the way to go. The drawback of using hash tables is that the memory usage is higher than the solution that uses sorting.

function sameLetters(str1, str2){   var hash = {};    var len1 = str1.length;   var len2 = str2.length;    // Strings with different lengths can't contain the same letters   if(len1 !== len2) return false;    // Count how many times each character appears in str1   for(var i = 0; i < len1; ++i) {     var c =  str1[i];     if(typeof hash[c] !== 'undefined') hash[c]++;     else hash[c] = 1;   }    // Make sure each character appearing in str2 was found in str1   for(var i = 0; i < len2; ++i) {     var c =  str2[i];     if(typeof hash[c] === 'undefined') return false;     if(hash[c] === 0) return false;     hash[c]--;   }    // Make sure no letters are left   for(var c in hash) {     if(hash[c]) return false;   }        return true; } 

You can then call the function like this (play with it in the browser console):

sameLetters("hello", "ehlol"); // true sameLetters("hello", "ehllol"); // false