Python中是否有O(1)时间复杂度的删除字符串最后一个字符的方法？

问题1：string = string[:-1]的时间复杂度是O(1)吗？ #

不是，该操作时间复杂度为O(n)，n是原字符串的长度。
核心原因是Python中的字符串属于不可变对象，所有对字符串内容的修改都需要创建全新的字符串对象，[:-1]切片需要完整复制原字符串除最后一位外的所有字符，耗时随字符串长度线性增长，不可能达到O(1)。

问题2：Python中有没有O(1)时间复杂度删除字符串最后一个字符的简便方法？ #

• 原生str类型没有对应实现：不可变的设计决定了只要最终输出还是str类型，就不可能实现O(1)的末尾删除操作。
• 如果你的场景需要频繁执行末尾增删操作，可以使用可变序列类型替代，相关方案如下：
  • 转列表处理：列表的pop()方法删除末尾元素是标准O(1)操作，示例：

    origin_str = "test_str"
    str_list = list(origin_str)
    str_list.pop() # O(1)时间完成末尾删除
    # 需要转回字符串时再执行join
    new_str = ''.join(str_list)
    

  • 若处理的是字节内容，可使用bytearray：作为可变字节序列，它的pop()删除末尾操作也是O(1)。
  • 高频两端操作场景可使用collections.deque：双端队列的头尾增删操作时间复杂度均为O(1)。

内容的提问来源于stack exchange，提问作者Mx321