时间戳

首页 > 解决方案 > 返回一个字符串的副本，其中列表内的索引被一个字符替换

python - 返回一个字符串的副本，其中列表内的索引被一个字符替换

问题描述

说我有一个清单indices。我也有性格char。第三个参数是一个字符串string。我想为所有人返回一份string这样的副本。string[index] = charindex in indices

我确实有一个功能可以做到这一点，但我认为它效率低下。这是

newString = string
for index in indices:
    newString = newString[:index] + char + newString[index+1:]

第一行复制字符串。然后它遍历所有需要更改的索引并使索引等于char。

根据这个问题，对字符串进行切片的效率是O(n)，那么上面代码的效率就是O(nm)，其中n是字符串的长度，m是 的长度indices。我希望有一个更快的解决方案。

任何改进将不胜感激。

编辑：一个例子是string = "qwertyuoip", indices = [0, 4, 5, 8], char = "1". 然后将字符串的第 0、4、5、8 个字符替换为 char。输出应该是newString = "1wer11ui1p".

标签： pythonstring

解决方案

这是使用可变列表的解决方案：

def replace_indices(s, indices, char):
    chars = list(s)
    for i in indices:
        chars[i] = char
    return ''.join(chars)

解决方案分为三个部分：

  • 从字符串构建一个字符列表s。这需要 O( n ) 时间，其中n是 的长度s。
  • 遍历索引列表，在列表中的char每个索引处设置字符。这需要 O( m ) 时间，其中m是 的长度indices。
  • 加入列表以生成输出字符串。这需要 O( n ) 时间来构建长度为n的字符串。

总时间为 O( n + m )。这是最优的，因为该问题需要构建一个长度为n的字符串，并且您必须使用列表中的所有m索引。如果索引总是不同的，那么m <= n并且时间是 O( n )。

推荐阅读