1
\$\begingroup\$

This is an exercise in a book which ask me to implement

Write an in-place function to eliminate adjacent duplicates in a []string slice.

I am relatively new to golang and I am not sure if my implementation is correct and effective or not.

func removeAdj(strings []string) []string {
    for i := 0; i < len(strings); i++ {
        dup := false
        lastJ := i
        for j := (i + 1); j < len(strings); j++ {
            if strings[i] == strings[j] {
                dup = true
                lastJ = j
            } else {
                break
            }
        }

        if dup {
            strings[i] = ""
            first := strings[:i]
            second := strings[lastJ+1:]

            strings = append(first, second...)
            i = -1
        }
    }

    return strings
}

Tests:

Input:  [a z x x z y]
Output: [a y]
Input:  [g e e k s f o r g e e g]
Output: [g k s f o r]
Input:  [c a a a b b b a a c d d d d]
Output: []
Input:  [a c a a a b b b a c d d d d]
Output: [a c a c]
\$\endgroup\$
  • \$\begingroup\$ Are these the only instructions you got? It is not clear where the recursive suppression from your tests come from. It is also not clear why the last test does not simply return [a] since, after removing all bs, you can remove as and then cs. Can you clarify the problem statement and what hypothesis you took? \$\endgroup\$ – Mathias Ettinger May 15 at 9:39
2
\$\begingroup\$

Your implementation, to me at least, doesn't seem correct. You need to remove adjacent duplicates, but looking at your last example, the sequence acaaabbacdddd completely removes the b and d characters from the slice. You're also using an awful lot of code to do a simple thing. What I'd do is quite simply this:

  • Iterate over the slice from index 0 to the next to last character
  • For each character, iterate over the remainder of the slice (nested loop) until you find a character that doesn't equal the current index
  • For each character at the current position + 1 that matches the current one, remove it, as it's an adjacent duplicate.

The code itself is quite simple:

func dedup(s []string) []string {
    // iterate over all characters in slice except the last one
    for i := 0; i < len(s)-1;i++ {
        // iterate over all the remaining characeters
        for j := i+1; j < len(s); j++ {
            if s[i] != s[j] {
                break // this wasn't a duplicate, move on to the next char
            }
            // we found a duplicate!
            s = append(s[:i], s[j:]...)
        }
    }
    return s
}

Given an input like [g e e k s f o r g e e g], the output of this is [g e k s f o r g e g]

Demo

The only trickery here is this line: s = append(s[:i], s[j:]...). What this effectively does is reassign the slice s to contain i values starting at 0 (so if i is 2, the slice will be [g, e]). The second part is creating a slice starting at j, until the end of s. Again, if j is 2, this slice will be all values starting at offset 2 until the end ([e k s f o r g e e g]).

So let's look at an actual example:

  • i == 1
  • j == i+1 (2)
  • s[i] == e, s[j] ==e`

We have a duplicate, so we'll reassign s like so:

 s = append(s[:1], s[2:]...)`

This means we're appending [e k s f o r g e e g] to [g], removing the duplicate e. Job done.


Note:

I've used []string here, but it should go without saying that a slice of characters is probably best represented as either []byte or []rune (for full UTF-8 support). Regardless of the type you end up using, the code above will work with with any type that can be compared with the == operator

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.