相关疑难解决方法(0)

我正在研究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 …

我正在运行 Python 2.7.10。

我需要拦截列表中的更改。我所说的“更改”是指在浅层意义上修改列表的任何内容（如果列表由相同顺序的相同对象组成，则不会更改，而不管这些对象的状态如何；否则，则更改）。我不需要找出列表是如何改变的，只需要知道它已经改变了。所以我只是确保我可以检测到它，并让基本方法完成它的工作。这是我的测试程序：

class List(list):
    def __init__(self, data):
        list.__init__(self, data)
        print '__init__(', data, '):', self

    def __getitem__(self, key):
        print 'calling __getitem__(', self, ',', key, ')',
        r = list.__getitem__(self, key)
        print '-->', r
        return r

    def __setitem__(self, key, data):
        print 'before __setitem__:', self
        list.__setitem__(self, key, data)
        print 'after  __setitem__(', key, ',', data, '):', self

    def __delitem__(self, key):
        print 'before __delitem__:', self
        list.__delitem__(self, key)
        print 'after  __delitem__(', key, '):', self

l = List([0,1,2,3,4,5,6,7]) #1
x = l[5]                    #2
l[3] …