讨论/《递归》 - 反转字符串/
《递归》 - 反转字符串

看了排名靠前几个答案,都用了 tmp 这个变量,我感觉这个也是多余的。我贴个不用 tmp 变量的写法。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        n = len(s)
        def helper(start: int):
            if start == n:
                return
            c = s[start]
            helper(start + 1)
            s[n - 1 - start] = c
        helper(0)

我来编个物理意义:

  1. 拿起当前字母,
  2. 递归这个过程,
  3. 将字母放在目标位置上。

其实,你也可以这么看,这其实是个回溯法,或者说深度优先搜索,一直搜索到最后一个位置,然后把最后一个字符放到正确位置,然后回溯。

还有一种写法:

class Solution:
    def reverseString(self, s: List[str]) -> None:
        def reverse(i: int, j: int) -> None:
            if i < j:
                s[i], s[j] = s[j], s[i]
                reverse(i + 1, j - 1)
        reverse(0, len(s) - 1)

物理意义:

  1. 交换开头下标和结尾下标的字符,
  2. 递归处理中间剩下的字符。
3
展开全部 16 讨论