How to remove strings in list from another list?

Question

I have 2 list which names are listA and listB.

I want to remove strings in listB which are in listA, but I want to do this in this way:

if listA contains: "bar", "bar", "bar", "foo" and listB contains : "bar"

it removes only 1 bar and the result will be: "bar", "bar", "foo"

the code I wrote removes all "bar":

List<string> result = listA.Except(listB).ToList();

Zymogen

Does retaining some of the original list's order matter? – Chokecherry

Answer 1

You can try to remove it one by one:

foreach (var word in listB)
    listA.Remove(word);

The Remove method will only remove one element at a time and is not throwing exception (but returning false) when the item is not found: https://msdn.microsoft.com/en-us/library/cd666k3e(v=vs.110).aspx

Fold

You can avoid the Contains call using directly IndexOf to get the position – Crescin

It's inefficient, but you can make it at least use directly listA.Remove(word). No need of Contains. – Resolution

Answer 2

var listA = new List<string>() { "bar", "bar", "bar", "foo" };
var listB = new List<string>() { "bar" };

foreach (var word in listB){
  listA.Remove(word);
}

Umpteen

This is basically a copy of the @Fold answer posted 10+ minutes before yours – Resolution

Answer 3

This is a faster method but it is likely to change the order of elements of first list. Steps:

• Map the listA to a Dictionary<string, int> (let's call it listAMap), where key is the element of the list and value is the total number of times that value has occurred in listA;
• Iterate through listB and for every element of listB, if that element is in the listAMap, reduce its count;
• Get the keys of listMapA using Keys property of C# dictionaries, and iterate through all the keys. For every key which has positive value, add that key to another list a total of its count times. So if an entry is "bar" -> 2, then add "bar" twice in the new list.

Total run time of the algorithm is O(m + n), where m and n are number of elements in both the original lists. It is a better running time than other approaches mentioned here which have O(m * n) running time. Obviously this algorithm uses more space.

---

Supportive Code for the algorithm above:

//Step-1: Create the dictionary...
var listAMap = new Dictionary<string, int>();
foreach (var listAElement in listA)
{
    listAMap.ContainsKey(listAElement) ? listAMap[listAElement]++ : listAMap.Add(listAElement, 1);
}

// Step-2: Remove the listB elements from dictionary...
foreach (var listBElement in listB)
{
    if (listAMap.Contains(listBElement)) listAMap[listBElement]--;
}

//Step-3: Create the new list from pruned dictionary...
var prunedListA = new List<string>();
foreach (var key in listAMap.Keys)
{
    if (listAMap[key] <= 0) continue;
    for (var count = 0; count < listAMap[key]; count++)
    {
        prunedListA.Add(key);
    }
}

//prunedListA contains the desired elements now.

Comfit

I was thinking for something similar, but counting listB and then removing the items from listA tah match (and decrementing the matching count). Anyway, +1 for thinking about efficiency. – Resolution

@IvanStoev: We aren't matching items in list. We are doing an O(1) lookup in a dictionary. Seriously, the solution is very simple (Not that you can give a +2 on the answer). I should've added the code too. Will do when I access SO from laptop. – Comfit

@IvanStoev: The last thing that needs to be done now is that the code above be factored into a separate method so that its cleaner. – Comfit

Good point. But let me post the algorithm I had in mind. As I said, similar idea O(m+n), but w/o the reordering effect you are talking about. – Resolution

Btw, I wasn't planning to post it because most of the people like one liners and don't care for performance. But once you shared your thoughts :) – Resolution

@IvanStoev: You are right - people like one liners. Readability of code is very important. And at SO where multiple programers answer, it often becomes the difference between better answer and liked answer. – Comfit

Answer 4

Here is a more efficient way to do that:

var countB = new Dictionary<string, int>(listB.Count);
foreach (var x in listB)
{
    int count;
    countB.TryGetValue(x, out count);
    countB[x] = count + 1;
}
listA.RemoveAll(x =>
{
    int count;
    if (!countB.TryGetValue(x, out count)) return false;
    if (count == 1)
        countB.Remove(x);
    else
        countB[x] = count - 1;
    return true;
});

Resolution

You missed the step where you populate countB. – Comfit

@Comfit I did not - try and see (hint - the little line countB[x] = count + 1;) :) – Resolution

Oh I see... didn't know about this behavior of TryGetValue() in dictionaries. Learned something new. – Comfit