编写一个接收字符串列表并返回列表列表的函数-解网

问：

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

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

(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']]

Python 字符串列表性能嵌套列表

>>> 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']]

0赞 Jack Smith 1/22/2021 #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"]]

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

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

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

但是，这将以不同的顺序返回结果（由于必要的），并认为其可读性较差。sorted

编写一个接收字符串列表并返回列表列表的函数

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

评论

评论