时间戳

首页 > 解决方案 > 交换字符串中的单词（面试题）

python - 交换字符串中的单词（面试题）

问题描述

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

您将获得一个包含 2 个没有空格的单词的字符串和一个参数，该参数是第一个单词的长度。你的目标是交换这两个词。

示例：swap_words("stackoverflow", 5) >> "overflowstack"

时间复杂度：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 编写，据我所知，字符串是不可变的。所以我唯一能想到的就是将字符串转换为字符列表进行交换并从中创建一个新字符串。

那么我在这里错过了什么？根据这些要求，是否有解决该问题的方法？

标签： pythonstringswap

解决方案

我认为最有效的方法是像这样对字符串进行切片：

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

推荐阅读