编写一个接收字符串列表和 return 列表列表的函数

Question

对于这个具体问题，我找不到任何类似的解决方案。

写一个接收字符串列表和returns列表列表的函数，一组列表中的每个项目与该列表中的其他项目具有相同的字母（不同顺序）。

(abc, acb, aab, aba) --> ((abc, acb), (aab, aba))

这是我目前的代码，但不太正确，首先它在 O(n^2) 中运行，我需要 O(n) 中的解决方案其次，如果有超过 2 个相似点，则整个结果不正确。

def ex1(str_list: list = ()) -> list:
    result = []
        items = []
        for item in str_list:
            items.append(''.join(sorted(item)))
        for i in range(len(items)):
            for j in range(i):
                if items[i] == items[j]:
                    result.append([str_list[j], str_list[i]])

        return result

我寻求的解决方案是使用字典，时间复杂度为 O(n) 例如

输入：['abc', 'acb', 'aab', 'aba', 'bac']

输出：[['abc', 'acb', 'bac'], ['aab', 'aba']]

Answer 1

使用分组惯用语并使用排序字符串作为键：

>>> import collections
>>> data = ['abc', 'acb', 'aab', 'aba', 'bac']
>>> def group_by_letters(strings):
...     grouper = collections.defaultdict(list)
...     for string in strings:
...         grouper[tuple(sorted(string))].append(string)
...     return list(grouper.values())
...
>>> group_by_letters(data)
[['abc', 'acb', 'bac'], ['aab', 'aba']]

Answer 2

这是一个简单的工作示例：

from collections import defaultdict
from typing import List, Tuple


def string_key(string: str) -> Tuple[str, ...]:
    """Returns a key which is unique on the characters in the string (ignoring ordering)."""
    return tuple(sorted(string))


def group_by_chars(data: List[str]) -> List[List[str]]:
    """Group strings by the characters they contain, regardless of order."""
    result = defaultdict(list)
    for value in data:
        key = string_key(value)
        result[key].append(value)
    return list(result.values())


assert group_by_chars(["abc", "acb", "aab", "aba"]) == [["abc", "acb"], ["aab", "aba"]]

诀窍是定义一个函数，将属于同一组的值映射到同一键，并根据该键函数的输出将每个值放入桶中。

另一种方法是使用 sorted 和 itertools.groupby:

from itertools import groupby

from typing import List, Tuple


def string_key(string: str) -> Tuple[str, ...]:
    """Returns a key which is unique on the characters in the string (ignoring ordering)."""
    return tuple(sorted(string))


def alternate_group_by_chars(data: List[str]) -> List[List[str]]:
    result = []
    for _key, group in groupby(sorted(data, key=string_key), string_key):
        result.append(list(group))
    return result

然而，这将 return 导致不同的顺序（由于必要 sorted）并且认为其可读性较差。

编写一个接收字符串列表和 return 列表列表的函数

write a function that receives a list of strings and return list of lists

python

string

performance

list

nested-lists