Javascript equivalent of php's array_intersect?

Hi,

Let start of by having comma-separated strings with [a-z] words (no other characters):
var string1 = "apple,pear,banana,grape,strawberry";
var string2 = "strawberrry,raspberry,blueberry";

What is the most efficent way to determine which words are in both arrays. (assuming the strings are split on comma's)

regular expressions and split/join are fine ofcourse, but I rather avoid nested loops.

Any thoughs?

-r-
LVL 49
RoonaanAsked:
Who is Participating?
 
dakydConnect With a Mentor Commented:
I'm not sure, but doing an indexOf() on either of the strings seems like it would be roughly equivalent (performance-wise) to doing a full search of the split array.  I can't back it up, but that's just what gut instinct tells me.

Assuming string1 has m elements and string2 has n elements, my idea was to make an algorithm with O(m+n) rather than O(m*n).  So, split the strings, sort the resulting arrays, then do a linear search through the two arrays.  Since they're sorted, you never have to back-track, and each element in arr1 is compared to an element in arr2 once and only once.  Of course, if indexOf() is fast enough, it may not matter at all.  Regardless, hope that helps.

<script type="text/javascript">
var string1 = "apple,pear,banana,grape,strawberry";
var string2 = "strawberry,raspberry,blueberry";

var arr1 = string1.split(",").sort();
var arr2 = string2.split(",").sort();

var common = new Array();
for (var i = 0, n = arr1.length, j = 0, k = arr2.length; (i < n) && (j < k); i ++)
{
  if (arr1[i] == arr2[j])
  {
    common[common.length] = arr1[i];
    j ++;
  }
  else if (arr1[i] > arr2[j])
  {
    j ++;
    i --;
  }
}

alert(common.toString());
</script>
0
 
enachemcCommented:
say

var string_1 = "," + string1 + ";";
for (<each item in string2>) if(string_1.indexOf("," + item + ",") != -1) <common item>;
0
 
enachemcCommented:
Your algorithm is faster, but not O(m+n) (because of sorting). Sorting is at best O(m) + O(n).
0
 
RoonaanAuthor Commented:
I think I'll go with your code dakyd, with minor adjustment of using common.push(arra1[i]);

Thanks a lot

-r-
0
 
dakydCommented:
Oops, you're right, I hadn't thought about the sorting ... regardless, glad it helped.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.