Python中in运算符是否隐含嵌套循环？对应字符移除代码时间复杂度是多少

问题1：是否属于嵌套for循环场景 #

是，这属于隐式嵌套循环场景。
字符串属于Python的序列类型，x in 字符串的执行逻辑和其他序列类型一致，底层会遍历字符串的每个字符逐一比对匹配，本质就是在你外层的for循环内部，又隐含了一层遍历string1的循环。

问题2：时间复杂度计算 #

我们设string1的初始长度为n，string2的长度为m：

• 外层循环会遍历string2的所有字符，共执行m次
• 每次循环内的char in string1操作最坏需要遍历当前string1的所有字符，时间复杂度为O(n)
• 如果匹配到字符执行replace操作，同样需要遍历当前string1的所有字符完成替换，时间复杂度为O(n)

即使每次替换后string1长度会缩短，最坏情况下（比如string2的所有字符都不在string1中，不会触发替换，每次in都要遍历完整的初始string1），整体时间复杂度为 O(m*n)。

优化方案参考 #

你可以利用集合的O(1)查找特性把复杂度降到O(n+m)，实现代码如下：

def removeChars(string1, string2):
    # 先把string2的字符转成集合，查找开销降为O(1)
    char_set = set(string2)
    # 单次遍历string1过滤，仅保留不在集合里的字符
    return ''.join(c for c in string1 if c not in char_set)

因为题目限定了仅包含26个小写字母，这个优化的收益会更明显。

内容的提问来源于stack exchange，提问作者Ram Shankar Kumar