Python - 求交集字符串

Question

我尝试编写一个for循环函数，它接收两个字符串并返回按照第一个字符串中出现的顺序交集字符。

这是我尝试的代码：

def strIntersection(str1, str2):
    for i in str1:
        str3 = ''
        str3 = str3.join(i for i in str1 if i in str2 not in str3)
    return str3

str1 = 'asdfasdfasfd'
str2 = 'qazwsxedc'

strIntersection(str1,str2)

=> 'asdasdasd'

然而，我只希望交集字符仅出现一次，并按照第一个字符串的顺序排列，即“asd”。

有人能帮忙吗？

我在其他论坛上找到了一些类似的问题，但所有解决方案似乎都涉及列表，而我希望我的输出为字符串。

- bang

Answer 1

你可以使用Python的集合http://docs.python.org/library/stdtypes.html#set来完成这个任务，像这样：

>>> set("asdfasdfasfd") & set("qazwsxedc")
set(['a', 's', 'd'])

- supakeen

Answer 2

你想要一个字符串，其中包含在str1和str2中都出现的唯一字符，并按它们在str1中出现的顺序排列。

唯一性和共同性意味着集合操作：也就是说，我们正在寻找同时出现在str1和str2中的字符集。集合本质上是无序的，但我们可以通过按照它们在str1中首次出现的"索引"对字符进行排序来重新排序数据。然后，只需从排序后的序列创建一个字符串即可。

将所有内容组合在一起，我们得到：

''.join(sorted(set(str1) & set(str2), key = str1.index))

- Karl Knechtel

Answer 3

检查另一种方式出现的情况，以控制顺序，并且不要发出已经发出的字符：

def strIntersection(s1, s2):
  out = ""
  for c in s1:
    if c in s2 and not c in out:
      out += c
  return out

当然你可以将其改写为列表推导式，但我认为这样更容易理解。

对于你的测试数据，我们得到：

>>> strIntersection('asdfasdfasfd' , 'qazwsxedc')
'asd'

- unwind

---

谢谢！这确实更容易理解。我现在意识到，我曾试图使用“join()”使它变得复杂化了。 - bang

''.join 是惯用法，非常简单。然而，在循环中使用它会失去重点。实际上，OP 代码中的 for 循环是完全无用的；它只是导致真正的工作 - str3 = str3.join(i for i in str1 if i in str2 not in str3) 多次执行，每次得到相同的结果，而且除了最后一次之外，每次都抛弃了结果。 - Karl Knechtel

你实际上不能将这个特定的算法重写为列表理解形式 - 至少不是在调用一些非常可疑的未记录的内容时 - 因为过滤步骤 c in s2 and c not in out 取决于到此为止的部分结果，这些结果不可访问（除非通过非常可疑的未记录的内容）。 - Karl Knechtel

我刚才评论说用列表替换“out”会加快速度，但是我进行了一些时间测试并确定它们没有效果，所以我删除了我的旧评论。我的计时显示这个解决方案每个循环使用10.7微秒，卡尔的解决方案每个循环使用16.7微秒，而我的修改后的“out = []”和“return "".join(out)”解决方案每个循环使用18.5微秒。 - Lauritz V. Thaulow

针对这些特定的字符串，或者说针对哪些测试数据？基于集合的方法可能需要相当长的字符串才能展现出优势。 - Karl Knechtel

Answer 4

最简单的方法是在Python中使用集合（sets）。

>>> a='asdfasdfasfd'
>>> b='qazwsxedc'
>>> set(a).intersection(b)
set(['a', 's', 'd'])

- Rohit Malgaonkar

---

这只是复制现有答案，并不能提供OP需要的排序功能。 - Mad Physicist

我们需要将字符串对象转换为集合才能进行比较吗？ - Alex Zubkov

Answer 5

看起来你的当前脚本如果你在第四行更正打字错误，应该可以实现它：

str3 = str3.join(i for i in str1 if i in str2 not in str3)

应该是

str3 = str3.join(i for i in str1 if i in str2 and i not in str3)

我不建议使用集合来处理这个问题，因为它们不能保证顺序。你的脚本也很可能会更快。

- aquavitae

---

我非常确定 OP 实际上想表达的是 (i for i in str1 if i in str2 and i not in str3)。但是这行代码无法正常工作，因为需要与之比较的 str3 还没有被构建出来。他试图同时使用 for 循环和推导式，逻辑混乱了。至于性能方面，对于长字符串，我肯定希望基于 set 的方法更快。 - Karl Knechtel

@Karl：是的，你说得对，我会更新我的回答。但与str3进行比较不应该有问题，因为它只需要检查已经构建好的部分。 - aquavitae

问题在于str3并不是“已经构建好的部分”。要么你在循环中执行这段代码，要么就不执行。如果你没有，在这种情况下，str3将会报UnboundLocalError - 你试图引用正在赋值的东西。如果你有一个循环，那么使用join和一个推导式就没有意义了，因为你只想考虑当前字符与已经找到的交叉字符，而不是整个字符串。 - Karl Knechtel

@Karl：我今天真的很糊涂啊！我读代码的时候，居然错过了str3 = ''和str3.join(...)两个地方。我还以为是在一个循环里呢。 - aquavitae

Answer 6

def str_intersection(str1, str2):
    common_letters = set(str1) & set(str2)
    str3 = ''
    for c in str1:
        if (c in common_letters) and (c not in str3):
            str3 += c
    return str3

- vartec

Answer 7

所有的回答都有帮助，但是你可能需要忽略或不忽略顺序。这可能很重要，特别是在查找拼写错误时。下面是更复杂的字符串交集查找函数版本：

def str_intersection(str_left, str_right, ignore_order = True ):
    common_letters = set(str_left) & set(str_right)
    str_intersected = ''
    for c in str_left:
        if (c in common_letters) and (c not in str_intersected):
            str_intersected += c
    if ignore_order:
        pass
    else:
        if str_intersected in str_left and str_intersected in str_right:
            return str_intersected
        else:
            return None
    return str_intersected

如果你运行 str_intersection("AB","XAB") 结果会是 AB。但是这种方式的主要缺陷在于，运行 str_intersection("god","dog") 的结果会是 god。如果你想得到无结果的话，可以这样使用该函数：str_intersection("god", "dog", ignore_order=False)，那么结果将会是None，因为 god 和 dog 共享相同的字符，但顺序不同。我希望这个复杂的函数可以帮到您。

- Suat Atan PhD