[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2224
  • Last Modified:

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-
0
Roonaan
Asked:
Roonaan
  • 2
  • 2
1 Solution
 
enachemcCommented:
say

var string_1 = "," + string1 + ";";
for (<each item in string2>) if(string_1.indexOf("," + item + ",") != -1) <common item>;
0
 
dakydCommented:
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:
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

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

  • 2
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now