jQuery cleaning up two strings (compare string1 to string2 and remove items not uniq)

How do I remove the oldItems from the newItems string? (remove Blue and Gr开发者_开发百科een) newItems is generated from jQuery autocomplete and I would like to remove already selected items from the select list.

newItems = Blue \n Red \n Black \n Yellow \n Green \n
oldItems = Blue,Yellow,Orange,Green

Best regards. Asbjørn Morell.

One algorithm would be to look at each of the oldItems and search for them in the newItems array. However, if you expect these arrays to reach any length, this is going to be O(n^2). This is essentially the algorithm given by Jacob Relkin.

However, instead, if you sort the two lists, you can do it faster.

var newArray = newItems.split("\n").sort();
var oldArray = oldItems.split(",").sort();
var newUniq = [];

var newLength = newArray.length;
var oldLength = oldArray.length;

var oldI = 0;
var newI = 0;
while (newI < newLength && oldI < oldLength) {
   var oldString = oldArray[oldI].trim();
   var newString = newArray[newI].trim();
   if (oldString == "") {
      oldI++;
   } else if (newString == "") {
      newI++;
   } else if (oldString == newString) {
      /* We only update newI, because if there are multiple copies of the 
       * same string in newItems, we want to ignore them all. */
      newI++;
   } else if (oldString < newString) {
      oldI++;
   } else { /* newArray[newI] < oldArray[oldI] */
      newUniq.push(newArray[newI]);
      newI++;
   }
}
while (newI < newLength) {
   newUniq.push(newArray[newI]);
   newI++;
}

newItems = newUniq.join(" \n ");

This walks through the two lists looking for duplicates in the new list in the old list. This should be O(n log n) because of the two sort operations.