python - 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。

订单N:

from collections import defaultdict

def find_char_fast(string1, string2):
    d = defaultdict(int)

    for char in string2:
        d[char] += 1

    res = []

    for char in string1:
        if char in d:
            res.append(char)

    return ''.join(res)

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

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

Answer 1

您的解决方案在算法上是正确的(第一个是 O(n**2)，第二个是 O(n))，但您正在做的一些事情可能会成为面试官的危险信号。

第一个功能基本没问题。你可能会因为这样写而获得加分:

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

..本质上做同样的事情。

我的问题(如果我穿着我的面试官裤)关于你如何编写 second 函数是你在你不关心的地方使用了 defaultdict完全不关心计数 - 你只关心成员资格。这是何时使用 set 的经典案例。

seen = set(string2)

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

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