Problem description

Implement an algorithm that flips a given string (you can use a single procedure variable) without using additional data structures and storage space.

Their thinking

Since additional data interfaces and storage space are not allowed, we flip a string backwards and forwards on an intermediate character axis, assigning STR [len] to STR [0] and STR [0] to STR [len].

Note: String may contain Chinese characters, so string must be converted to rune.

func reverseString(s *string) {
        str := []rune(*s)
        n := len(str)
        for i := 0; i < n / 2; i++ {
                str[i], str[n - i - 1] = str[n - i - 1], str[i]
        }
        *s = string(str)
}
Copy the code

test

s := "123456789"
reverseString(&s)
fmt.Println(s)

/ / output:
/ / 987654321
Copy the code

extension

Suppose we have a function that reverses a string, reverseString(), and we want to use it to put the first m characters of a string at the end of the string, assuming a string of length N. What do we do?

For example, change 123456789 to 456789123

We can flip the first three characters, then the last six characters, and finally the entire string.

s := "123456789"
s1 := s[:3]
s2 := s[3:]
reverseString(&s1)
reverseString(&s2)
s = s1 + s2
reverseString(&s)
fmt.Println(s)

/ / output:
/ / 456789123
Copy the code