用字符串交换单词(面试问题)

Question

我遇到了一个没有解决方案的面试问题，我找不到满足内存和运行时要求的解决方案。

给你一个没有空格的两个字的字符串和一个参数，这个参数是第一个单词的长度。你的目标是在适当的地方交换两个单词。

示例:swap_words(“堆栈溢出”，5) >>“溢出堆栈”

时间复杂度: O(N)，内存复杂度: O(1)

我设法用递归来解决这个问题:首先，我将较短的单词移到它的位置，然后用较长的单词重复这个过程。

swap_words("stackoverflow ", 5)
stackoverflow >> rflowovestack 

swap_words("rflowove", 3)   # 13-5-5
rflowove >> oveowrfl        ###  ove-owrfl-stack 

swap_words("owrfl", 2)      # 8-3-3
owrfl >> flrow              ###  ove-flr-owstack

swap_words("flr", 1)        # 5-2-2
flr >> rlf                  ###  overlfowstack

这里的调用堆栈显然不是O(1)内存。

我在某个地方看到的另一个解决方案是镜像整个字符串，然后分别镜像每个单词：

stackoverflow >> wolfrevokcats
wolfrevo--kcats >> overflow--stack

在我看来，这要好得多，但我不知道如何在不使用额外空格的情况下在字符串中交换字符。我是用Python编写的，据我所知，字符串是不可变的。因此，我唯一能想到的就是将字符串转换为一个字符列表，然后进行交换，并从中创建一个新的字符串。

我在这里错过了什么？在这些要求下，是否有解决这个问题的办法？

Answer 1

在我看来，最有效的方法是像这样分割字符串：

def swap_words(word, n):
    return word[n:] + word[:n]