Python中字符串中的字符

Question

Implement a function with signature find_chars(string1, string2) that takes two strings and returns a string that contains only the characters found in string1 and string two in the order that they are found in string1. Implement a version of order N*N and one of order N.

（来源：http://thereq.com/q/138/python-software-interview-question/characters-in-strings）

以下是我的解决方案：

订单N*N：

def find_chars_slow(string1, string2):
    res = []
    for char in string1:
        if char in string2:
            res.append(char)

    return ''.join(res)

所以for循环遍历N个元素，每个char in string2检查都是另一个N个操作，因此得到N*N

订单号：

^{pr2}$

首先将string2的字符存储为字典（O（N））。然后扫描string1（O（N））并检查它是否在dict（O（1））中。这给出了O（2N）=O（N）的总运行时间。在

以上是正确的吗？有没有更快的方法？在

Answer 1

你用过的算法非常好。你能做的改进很少

1. 因为您要将第二个字符串转换为字典，所以我建议使用set，如下所示

   d = set(string2)
   

2. 除此之外，您可以使用列表理解作为过滤器，如下所示

   return "".join([char for char in string1 if char in d])
   

3. 如果输出中字符的顺序无关紧要，您可以简单地将两个字符串转换为集合，然后简单地查找集合差，如下所示

   return "".join(set(string1) - set(string2))
   

Answer 2

你的解决方案在算法上是正确的（第一个是O（n**2），第二个是O（n）），但你做的一些事情可能会给面试官带来危险。在

第一个功能基本上没问题。你这样写可能会得到加分：

''.join([c for c in string1 if c in string2])

…基本上是一样的。在

我的问题是（如果我穿着面试官的裤子）你如何编写second函数，你使用的是一个你根本不关心计数的defaultdict，你只关心成员资格。这是何时使用set的典型例子。在

^{pr2}$

我编写这些函数的方式将比您编写的稍快一些，因为列表理解是在本机代码中循环，而不是在python字节码中循环。它们在算法上具有相同的复杂性。在

Answer 3

显然，每个方法的复杂度都比你的方法少一次。在

这并不是说没有一种方法可以运行得更快。没有必要在字典里增加数字。例如，可以使用set。您还可以进一步使用python的特性，例如列表理解/生成器：

def find_char_fast2(string1, string2):
    s= set(string2)
    return "".join( (x for x in string1 if x in s) )