复制给定字符串中的每个 space

Question

我在很多面试中发现了以下问题（不是我的面试）。

给定一个字符串，你需要用 2 个 space 替换每个 space。您可能会假设您的字符串有足够的空间来添加所需的 space。需要原地做，不允许分配内存

我不明白如何在没有覆盖字母的情况下实现这一点。

Answer 1

你的问题没有太多上下文。假设这是一次编程面试，您正在处理一种低级语言，如 C 或汇编程序。我们还假设该字符串的计数 and/or 以 null 结尾，例如 'this is a string[=17=][=17=][=17=][=17=]'

我会从头到尾扫描字符串并计算 spaces，我们称其为 C。然后我会在字符上向后遍历字符串，将每个字符向前移动 C 个位置。每遇到一个space，将space向前复制C个位置，C减一，再将space移动C个位置。当C为0时停止。

这里，nulls/unused用句点表示。

this is a string....  C=3
this is a string..g.
this is a string.ng.
this is a stringing.
this is a strinring.
this is a stritring.
this is a strstring.
this is a st string.
this is a s  string. C=2
this is a a  string.
this is   a  string.
this iss  a  string.  C=1
this iis  a  string.  
this  is  a  string.  C=0

Answer 2

找到 space 后的字符串需要移动一个字母。为了减少减少移动部分所需的时间，我会使用这种方法：

数一数space的个数。我将此计数称为 c.
将字符串向右移动 space 的数量（我假设这里是从左到右的阅读方向。）
从偏移量 c 开始循环，直到字符串结束：
1. 为已复制的 space 初始化一个计数器，称为 s，值为 0
2. 将当前位置的字母复制到当前位置 - c + s
3. 如果字母是 space，递增 s 并添加 space 到位置 - c + 1

不确定我脑海中是否正确计算了所有偏移量，如果需要请更正。但是因为这只是一个面试问题，所以想法只是勾勒出一个正确的算法。

复制给定字符串中的每个 space

duplicate each space in a given string

string

in-place