How to find the difference between two slices of strings

Here is my desired outcome

slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}

difference(slice1, slice2)
=> ["hello"]

I am looking for the difference between the two string slices!

Assuming Go maps are ~O(1), here is an ~O(n) difference function that works on unsorted slices.

// difference returns the elements in `a` that aren't in `b`.
func difference(a, b []string) []string {
    mb := make(map[string]struct{}, len(b))
    for _, x := range b {
        mb[x] = struct{}{}
    }
    var diff []string
    for _, x := range a {
        if _, found := mb[x]; !found {
            diff = append(diff, x)
        }
    }
    return diff
}

Depending on the size of the slices, different solutions might be best.

My answer assumes order doesn't matter.

Using simple loops, only to be used with smaller slices:

package main

import "fmt"

func difference(slice1 []string, slice2 []string) []string {
	var diff []string

	// Loop two times, first to find slice1 strings not in slice2,
	// second loop to find slice2 strings not in slice1
	for i := 0; i < 2; i++ {
		for _, s1 := range slice1 {
			found := false
			for _, s2 := range slice2 {
				if s1 == s2 {
					found = true
					break
				}
			}
			// String not found. We add it to return slice
			if !found {
				diff = append(diff, s1)
			}
		}
		// Swap the slices, only if it was the first loop
		if i == 0 {
			slice1, slice2 = slice2, slice1
		}
	}

	return diff
}

func main() {
	slice1 := []string{"foo", "bar", "hello"}
	slice2 := []string{"foo", "world", "bar", "foo"}

	fmt.Printf("%+v\n", difference(slice1, slice2))
}

Output:

[hello world]

Playground: http://play.golang.org/p/KHTmJcR4rg

I use the map to solve this problem

package main

import "fmt"

func main() {
	slice1 := []string{"foo", "bar","hello"}
	slice2 := []string{"foo", "bar","world"}

	diffStr := difference(slice1, slice2)

	for _, diffVal := range diffStr {
		fmt.Println(diffVal)
	}

}

func difference(slice1 []string, slice2 []string) ([]string){
	diffStr := []string{}
	m :=map [string]int{}

	for _, s1Val := range slice1 {
		m[s1Val] = 1
	}
	for _, s2Val := range slice2 {
		m[s2Val] = m[s2Val] + 1
	}

	for mKey, mVal := range m {
		if mVal==1 {
			diffStr = append(diffStr, mKey)
		}
	}

	return diffStr
}

output:
hello
world

func diff(a, b []string) []string {
    temp := map[string]int{}
    for _, s := range a {
        temp
展开收缩
++
    }
    for _, s := range b {
        temp
展开收缩
--
    }

    var result []string
    for s, v := range temp {
        if v != 0 {
            result = append(result, s)
        }
    }
    return result
}

If you want to handle duplicated strings, the v in the map can do that. And you can pick a.Remove(b) ( v>0 ) or b.Remove(a) (v<0)

func unique(slice []string) []string {
    encountered := map[string]int{}
    diff := []string{}

    for _, v := range slice {
        encountered[v] = encountered[v]+1
    }

    for _, v := range slice {
        if encountered[v] == 1 {
	    diff = append(diff, v)
        }
    }
    return diff
}

func main() {
	slice1 := []string{"hello", "michael", "dorner"}
	slice2 := []string{"hello", "michael"}
	slice3 := []string{}
	fmt.Println(unique(append(slice1, slice2...))) // [dorner]
	fmt.Println(unique(append(slice2, slice3...))) // [michael michael]
}

As mentioned by ANisus, different approaches will suit different sizes of input slices. This solution will work in linear time O(n) independent of input size, but assumes that the "equality" includes index position.

Thus, in the OP's examples of:

slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}

The entries foo and bar are equal not just due to value, but also due to their index in the slice.

Given these conditions, you can do something like:

package main

import "fmt"

func difference(s1, s2 []string) string {
	var (
		lenMin  int
		longest []string
		out     string
	)
	// Determine the shortest length and the longest slice
	if len(s1) < len(s2) {
		lenMin = len(s1)
		longest = s2
	} else {
		lenMin = len(s2)
		longest = s1
	}
	// compare common indeces
	for i := 0; i < lenMin; i++ {
		if s1[i] != s2[i] {
			out += fmt.Sprintf("=>\t%s\t%s\n", s1[i], s2[i])
		}
	}
	// add indeces not in common
	for _, v := range longest[lenMin:] {
		out += fmt.Sprintf("=>\t%s\n", v)
	}
	return out
}

func main() {
	slice1 := []string{"foo", "bar", "hello"}
	slice2 := []string{"foo", "bar"}
	fmt.Print(difference(slice1, slice2))
}

Produces:

>> => hello

Playground

If you change the slices to be:

func main() {
	slice1 := []string{"foo", "baz", "hello"}
	slice2 := []string{"foo", "bar"}	
	fmt.Print(difference(slice1, slice2))
}

It will produce:

>> => baz bar
=> hello

Most of the other solutions here will fail to return the correct answer in case the slices contain duplicated elements.

This solution is O(n) time and O(n) space if the slices are already sorted, and O(n*log(n)) time O(n) space if they are not, but has the nice property of actually being correct. 🤣

func diff(a, b []string) []string {
	a = sortIfNeeded(a)
	b = sortIfNeeded(b)
	var d []string
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		c := strings.Compare(a[i], b[j])
		if c == 0 {
			i++
			j++
		} else if c < 0 {
			d = append(d, a[i])
			i++
		} else {
			d = append(d, b[j])
			j++
		}
	}
	d = append(d, a[i:len(a)]...)
	d = append(d, b[j:len(b)]...)
	return d
}

func sortIfNeeded(a []string) []string {
	if sort.StringsAreSorted(a) {
		return a
	}
	s := append(a[:0:0], a...)
	sort.Strings(s)
	return s
}

If you know for sure that the slices are already sorted, you can remove the calls to sortIfNeeded (the reason for the defensive slice copy in sortIfNeeded is because sorting is done in-place, so we would be modifying the slices that are passed to diff).

See https://play.golang.org/p/lH-5L0aL1qr for tests showing correctness in face of duplicated entries.

I have this example but it works only for the elements of the first array "not present" in the second array

with generics

type HandleDiff[T comparable] func(item1 T, item2 T) bool

func HandleDiffDefault[T comparable](val1 T, val2 T) bool {
	return val1 == val2
}

func Diff[T comparable](items1 []T, items2 []T, callback HandleDiff[T]) []T {
	acc := []T{}
	for _, item1 := range items1 {
		find := false
		for _, item2 := range items2 {
			if callback(item1, item2) {
				find = true
				break
			}
		}
		if !find {
			acc = append(acc, item1)
		}
	}
	return acc
}

usage

diff := Diff(items1, items2, HandleDiffDefault[string])

I would add a small change to the solution by @peterwilliams97, so that we can ignore the order of the input.

func difference(a, b []string) []string {
	// reorder the input,
	// so that we can check the longer slice over the shorter one
	longer, shorter := a, b
	if len(b) > len(a) {
		longer, shorter = b, a
	}

	mb := make(map[string]struct{}, len(shorter))
	for _, x := range shorter {
		mb[x] = struct{}{}
	}
	var diff []string
	for _, x := range longer {
		if _, found := mb[x]; !found {
			diff = append(diff, x)
		}
	}
	return diff
}

Input: s1 = ["this", "apple", "is", "sweet"], s2 = ["this" "apple" "is" "sour"]

Output: ["sweet","sour"]

func difference(s1, s2 []string) []string {
	combinedSlice := append(s1, s2...)
	dm := make(map[string]int)
	for _, v := range combinedSlice {
		if _, ok := dm[v]; ok {
			// remove element later as it exist in both slice.
			dm[v] += 1
			continue
		}
		// new entry, add in map!
		dm[v] = 1
	}
	var retSlice []string
	for k, v := range dm {
		if v == 1 {
			retSlice = append(retSlice, k)
		}
	}
	return retSlice
}

// If we needs difference from first slice use below funcion.

// Output: [sweet]

func diff(s1, s2 []string) []string {
	mp1 := make(map[string]bool)
	for _, v := range s2 {
		mp1[v] = true
	}
	var dif []string
	for _, v1 := range s1 {
		if _, ok := mp1[v1]; !ok {
			dif = append(dif, v1)
		}
	}
	return dif
}

The code below gives the absolute difference between strings regardless of the order. Space complexity O(n) and Time complexity O(n).

// difference returns the elements in a that aren't in b
func difference(a, b string) string {
	longest, shortest := longestString(&a, &b)
	var builder strings.Builder
	var mem = make(map[rune]bool)
	for _, s := range longest {
		mem
展开收缩
 = true
	}
	for _, s := range shortest {
		if _, ok := mem
展开收缩
; ok {
			mem
展开收缩
 = false
		}
	}
	for k, v := range mem {
		if v == true {
			builder.WriteRune(k)
		}
	}
	return builder.String()
}
func longestString(a *string, b *string) ([]rune, []rune) {
	if len(*a) > len(*b) {
		return []rune(*a), []rune(*b)
	}
	return []rune(*b), []rune(*a)
}