怎么用递归解决《344. 反转字符串》

发表于 分类于 阅读次数： 本文字数： 314 阅读时长 ≈ 1 分钟

这个题目太简单了，我就不贴题目的原文了。意思是这样的，给你一个字符数组（字符串），然后，你要原地把这个数组的元素顺序反转。这道题目是非常平凡的，常规解法是使用双指针，头尾指针向中间夹逼，交换头尾指针指向的字符。

1
2
3
4
5
6
7
class Solution:
    def reverseString(self, s: List[str]) -> None:
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -=

用 Python 写，会非常短小。时间复杂度是 O(n)，空间复杂度是 O(1)。

假如，让你为这个题目设计一个递归算法，你会怎么写呢？

方案一：假设我们掌握了一个把下标 [i, j] 范围内的字符顺序反转的方法。

那么对于这个题目来说，我们只要交换头尾两个字符，然后，用递归方法去计算中间剩余部分即可。

1
2
3
4
5
6
7
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
4
5
6
7
8
9
10
class Solution:
    def reverseString(self, s: List[str]) -> None:
        n = len(s)
        def dfs(i: int):
            if i == n:
                return
            c = s[i]
            dfs(i + 1)
            s[n - 1 - i] = c
        dfs(0

这里很有意思的一点，就是这个变量 c 可不可以不要？为什么？

你还能想出其他的递归设计方法么？欢迎给我留言。