翻转字符串

翻转字符串

问题描述

请实现一个算法，在不使用【额外数据结构和储存空间】的情况下，翻转一个给定的字符串(可以使用单个过程变量)。

给定一个string，请返回一个string，为翻转后的字符串。保证字符串的长度小于等于5000。

解题思路

一种常见的解题思路是使用双指针法。定义两个指针，一个指向字符串的开头，一个指向字符串的末尾。然后交换两个指针所指向的字符，然后两个指针向中间移动，重复这个过程，直到两个指针相遇。

源码分析

func reverseString(s string) string {
    str := []byte(s)
    left := 0
    right := len(str) - 1

    for left < right {
        str[left], str[right] = str[right], str[left]
        left++
        right--
    }

    return string(str)
}

多种解题思路

除了使用双指针法，还可以使用递归法来翻转字符串。

func reverseString(s string) string {
    str := []byte(s)
    return string(reverse(str, 0, len(str)-1))
}

func reverse(str []byte, left, right int) []byte {
    if left >= right {
        return str
    }

    str[left], str[right] = str[right], str[left]
    return reverse(str, left+1, right-1)
}

这种方法通过递归地交换字符串的首尾字符，直到首尾指针相遇，完成字符串的翻转。