Как найти разницу между двумя фрагментами строк в Голанге?

Ответ 1

В зависимости от размера срезов различные решения могут быть лучшими.

Мой ответ предполагает, что порядок не имеет значения.

Использование простых циклов, только для небольших фрагментов:

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))
}

Вывод:

[hello world]

Игровая площадка: http://play.golang.org/p/KHTmJcR4rg

Ответ 2

Предполагая, что карты Go имеют значение ~ O (1), здесь есть разностная функция ~ O (n), которая работает на несортированных срезах.

// 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
}

Ответ 3

Я использую карту для решения этой проблемы

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
}

Выход:
привет
мир

Ответ 4

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]
}

Ответ 5

Как упомянутый ANisus, разные подходы будут соответствовать разным размерам входных фрагментов. Это решение будет работать в линейном времени O(n) независимо от размера ввода, но предполагает, что "равенство" включает положение индекса.

Таким образом, в примерах OP:

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

Записи foo и bar равны не только значению, но также и их индексу в срезе.

Учитывая эти условия, вы можете сделать что-то вроде:

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))
}

Выдает:

= > привет

Игровая площадка

Если вы измените фрагменты:

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

Он будет производить:

= > baz bar
  = > привет

Ответ 6

Приведенный ниже код дает абсолютную разницу между строками независимо от порядка. Пространственная сложность O (n) и временная сложность 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)
}

Ответ 7

Большинство других решений здесь не смогут вернуть правильный ответ, если срезы содержат дублированные элементы.

Это решение - O (n) время и O (n) пространство, если срезы уже отсортированы, и O (n * log (n)) время O (n) пространство, если они не являются, но имеет приятное свойство на самом деле быть правильный. 🤣

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
}

Если вы точно знаете, что фрагменты уже отсортированы, вы можете удалить вызовы sortIfNeeded (причина для защитной копии фрагмента в sortIfNeeded заключается в том, что сортировка выполняется на месте, поэтому мы будем изменять фрагменты, передаваемые в diff).

См. Https://play.golang.org/p/lH-5L0aL1qr для тестов, показывающих правильность в отношении дублированных записей.