Golang Project Structure

Tips and tricks for writing and structuring Go code

Reversing a String

Language

  • unknown

by

This post will look at various ways to reverse a string in Go, a fairly common task that isn’t explicitly handled by the standard library.

We will start by looking at some basic examples using Java and the Linux command line, then we will go through various ways to code solutions to the problem in Go itself.

We will also consider some complications that relate to the Unicode character encoding used by Go strings.

Language Envy

Some programming languages have a native method or function that can be called to reverse the order of a string, so that its last character — or rune — becomes the first and vice versa, with every character in between also shifted a corresponding number of places.

Go isn’t one of these languages (at least, not at the current time of writing this post, but such a method could conceivably be introduced into future versions).

Reversing a string in computer code can be a complicated operation, but it doesn’t need to be as complicated as untangling a physical ball of string.

If you want to reverse a string in Java, for example, you can simply call the reverse method on the StringBuilder class, as shown below:

public class Example {
	public static void main(String []args) {
		String originalText = "green with envy";
		String reversedText = new StringBuilder(originalText).reverse().toString();
        
		System.out.println(reversedText);
	}
}

Running the Java code above will produce the following output:

yvne htiw neerg

Needless to say, if you read that text back-to-front, you will get our original message.

Using Linux Commands

That isn’t to say that you can’t piggyback on string-reversal code written by other people in your Go code, however.

If you’re working on a Linux machine, for example, you can call a system command to do the work for you, like so:

package main

import (
	"log"
	"os"
	"os/exec"
)

func main() {
	cmd := exec.Command("/bin/bash", "-c", `echo "spin me around" | rev`)

	cmd.Stdout = os.Stdout

	if err := cmd.Run(); err != nil {
		log.Fatalln(err)
	}
}

The first argument passed to exec.Command is the path to the program you want to execute, in this case the Bash shell interpreter — but you could, of course, use Z-Shell or KornShell instead.

The following arguments will be passed to the shell program. In this case, the "-c" option tells the interpreter to run any commands given as the following argument.

So echo `"spin me around" | rev` is the Linux command that our Bash shell instance will run.

The Simplest Way to Reverse a String in Go

Now let’s look at how to write our own function in Go that will reverse the runes in a string:

package main

func Reverse(input string) (output string) {
	for _, r := range input {
		output = string(r) + output
	}

	return 
}

This is a fairly elegant solution, since the work is contained within a single loop, which iterates through each of the runes in the input string, converting it to a string and prepending it to the output string (which, of course, is initially empty).

Despite its evident elegance, this function could be quite inefficient when working with long strings of text, however, because strings are immutable data structures in Go, so new memory has to be allocated each time there is an assignment to the output string on every iteration of the loop.

Converting the String Into a Slice of Runes

Let’s have a look at another way to tackle the problem of reversing a string now.

If you were unsure how to reverse a string, but you did know how to reverse a slice, then you can simplify the problem simply by converting a string into a slice of runes and using the knowledge that you already have:

package main

func Reverse(input string) (output string) {
	inputRunes := []rune(input)

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

	output = string(inputRunes)

	return
}

We have already looked in a previous post at various ways to reverse a slice, so in the example above I’ve incorporated one of the reversal methods listed there.

Even though a slice of runes and a new string has to be allocated, this function uses many fewer memory allocations than the previous one, unless the input string is very small, so it will generally prove to be a better and more efficient solution to the problem.

Using Defer Functions

We could try yet another approach, however, by taking advantage of the way that defer functions are called in Go:

package main

import "strings"

func Reverse(input string) (output string) {
	var outputBuilder strings.Builder

	defer func() {
		output = outputBuilder.String()
	}()

	for _, r := range input {
		defer func(r rune) {
			outputBuilder.WriteRune(r)
		}(r)
	}

	return
}

When we use the defer keyword in Go, the function that follows is added to a stack by the compiler. Each element of this stack will be popped off when the function returns, which means that the functions will run in the opposite order to the one in which they were added.

The first defer function that’s declared will be the last to run, and the last defer function that’s declared will be the first to run.

So we can take advantage of this fact to help us reverse a string. We simply need to add defer functions that will write each rune of the string to a strings.Builder variable, knowing that they will be called in reverse order.

Notice how we start by setting a defer function that will generate the string from outputBuilder, since this is the last function that we want to run, when they’re popped from the stack in reverse order.

Taking Account of Unicode Encoding

In the previous examples, we have been assuming that each character uses only a single rune. This is generally but not necessarily true with Unicode strings.

For example, the single character in the string below requires four runes, as you will see if run the code:

package main

import (
	"fmt"
)

func main() {
	char := "é"

	fmt.Println(
		char,
		[]rune(char),
		len([]rune(char)),
	)
}

The updated version of our Reverse function shown below now takes proper account of multi-rune characters when reversing a string:

package main

func Reverse(input string) (output string) {
	inputRunes := []rune(input)
	inputRunesLength := len(inputRunes)

	if inputRunesLength <= 1 {
		output = input
		return
 	}

	i, j := 0, 0
	for i < inputRunesLength && j < inputRunesLength {
		j = i + 1

		for j < inputRunesLength && isUnicodeMark(inputRunes[j]) {
			j++
		}

		if isUnicodeMark(inputRunes[j-1]) {
			reverseRunes(inputRunes[i:j])
		}

		i = j
	}

	reverseRunes(inputRunes)

	output = string(inputRunes)
	return
}

func reverseRunes(inputRunes []rune) {
	for i, j := 0, len(inputRunes)-1; i < j; i, j = i+1, j-1 {
		inputRunes[i], inputRunes[j] = inputRunes[j], inputRunes[i]
	}
}

func isUnicodeMark(r rune) bool {
	return unicode.Is(unicode.Mn, r) ||
		unicode.Is(unicode.Me, r) ||
		unicode.Is(unicode.Mc, r)
}

As you can see, there are two helper functions above. The reverseRunes function simply reverses the order of a slice of runes, using the algorithm we saw earlier. The isUnicodeMark function determines whether the rune is a combining mark, which modifies the appearance of a character declared by a previous rune, rather than standing for a character itself.

Within the Reverse function, we first perform a simple validation check, since if the input string contains one or zero runes, it is, by definition, already in reverse order. In this case, we end the function early.

Then we check for blocks of runes that contain combining marks: we reverse each of these blocks, so that when we later reverse the entire string, the blocks of runes that make up a single character will still be in the correct order.

Finally, we use the reverseRunes helper function on all of the runes before converting them back into a string so that we can assign it to our output variable.

Calling the Functions

You should be able to call any one of the Reverse functions that we’ve worked on in the preceding examples like so:

package main

import (
	"fmt"
)

func main() {
	fmt.Println(Reverse("HELLO, GOPHERS!"))
}

Whichever version of the Reverse function you decide to use, running the code above should produce the following output:

!SREHPOG ,OLLEH

Playing With Palindromes for Extra Credit

If you want to attempt an additional coding exercise, you could try creating a function called isPalindrome that takes a string argument and returns a boolean value.

This function will return true if, and only if, the string reads the same backwards as it does forwards — in other words, if the string is palindromic.

So, for example, isPalindrome("racecar") and isPalindrome("evil olive") would both return true, whereas isPalindrome("irreversible") and isPalindrome("beneficent olive") would return false.

I suggest that you use one of the Reverse functions that we’ve already written in order to help with the palindrome-checking logic.

Leave a Reply

Your email address will not be published.