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!
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
", difference(slice1, slice2))
}
Output:
[hello world]
Playground: http://play.golang.org/p/KHTmJcR4rg
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
", s1[i], s2[i])
}
}
// add indeces not in common
for _, v := range longest[lenMin:] {
out += fmt.Sprintf("=>\t%s
", v)
}
return out
}
func main() {
slice1 := []string{"foo", "bar", "hello"}
slice2 := []string{"foo", "bar"}
fmt.Print(difference(slice1, slice2))
}
Produces:
=> hello
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
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
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
}
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]
}
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[s] = true
}
for _, s := range shortest {
if _, ok := mem[s]; ok {
mem[s] = 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)
}
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 {
temp := map[string]int{}
for _, s := range a {
temp[s]++
}
for _, s := range b {
temp[s]--
}
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)