DEV Community

Discussion on: Reverse a string: awful answers only

View post
Collapse
 
edh_developer profile image
edh_developer • • Edited

Go - convert the string to a slice of runes, swap the runes in the slice via some bit manipulation, then convert the slice back to string and return it.

Remember, to swap the values of two integers a and b...

a = a XOR b
b = a XOR b
a = a XOR b

func reverse(s string) string {
    characters := []rune(s)

    for i, j := 0, len(characters)-1; i < j; {
        characters[i] ^= characters[j]
        characters[j] ^= characters[i]
        characters[i] ^= characters[j]
        i++
        j--
    }

    return string(characters)
}
Enter fullscreen mode Exit fullscreen mode

Update: it occurred to me that the solution above may be odd, but it's not that inefficient. We can do better. So... take 2:

type charNode struct {
    C rune
    I int
}

func sortNodes(nodes []charNode) {

    var cn charNode

    for outer := len(nodes) - 1; outer > 0; outer-- {
        for inner := len(nodes) - 1; inner > 0; inner-- {
            if nodes[inner].I > nodes[inner-1].I {
                cn = nodes[inner]
                nodes[inner] = nodes[inner-1]
                nodes[inner-1] = cn
            }
        }
    }

}

func reverseViaSort(s string) string {
    nodes := make([]charNode, len(s))

    for i, r := range []rune(s) {
        nodes[i] = charNode{r, i}
    }

    sortNodes(nodes)
    sortedRunes := make([]rune, len(s))
    for i, n := range nodes {
        sortedRunes[i] = n.C
    }

    return string(sortedRunes)
}
Enter fullscreen mode Exit fullscreen mode

We split the string into a slice of ordered rune-index pairs, reverse the slice by sorting based on the indices, then get the resulting string from the reordered slice. It's pretty inefficient to begin with, and choosing bubblesort as our sorting algorithm gets us some O(N^2) fun.