小编use*_*964的帖子

我正在研究CTCI的一个问题.

第1章的第三个问题是你带一个字符串如

'Mr John Smith '

并要求您用以下内容替换中间空格%20:

'Mr%20John%20Smith'

作者在Python中提供了这个解决方案,称之为O(n):

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    counter = 0
    output = ''
    for char in string:
        counter += 1
        if counter > length:
            return output
        elif char == ' ':
            output = output + '%20'
        elif char != ' ':
            output = output + char
    return output

我的问题:

我理解这是从左到右扫描实际字符串的O(n).但是Python中的字符串不是不可变的吗？如果我有一个字符串,我用+操作符添加另一个字符串,它是否分配必要的空格,复制原始字符串,然后复制附加字符串？

如果我有一个n长度为1 的字符串集合,则需要:

1 + 2 + 3 + 4 …