字谜的乐趣（Python）

Question

字谜游戏的乐趣 描述

如果两个字符串是彼此的排列，则它们是字谜词。换句话说，两个字符串具有相同的大小和相同的字符。例如，“aaagmnrs”是“anagrams”的字谜词。给定一个字符串数组，删除作为较早字符串的字谜词的每个字符串，然后按排序顺序返回剩余的数组。

示例

str = ['代码', 'doce', 'ecod', 'framer', '框架']

“code”和“doce”是字谜词。从数组中删除“doce”并保留数组中第一次出现的“code”。 “code”和“ecod”是字谜词。从数组中删除“ecod”并保留数组中第一次出现的“code”。 “代码”和“成帧者”不是字谜。将两个字符串保留在数组中。 由于“framer”中额外的“r”，“framer”和“frame”不是字谜。将两个字符串保留在数组中。 按升序对剩余字符串进行排序：[“code”,“frame”,“framer”]。

功能说明

在下面的编辑器中完成函数 funWithAnagrams。

funWithAnagrams 有以下参数：

string text[n]:  an array of strings

退货：

string[m]:  an array of the remaining strings in ascending alphabetical order,.

限制

0 ≤ n ≤ 1000
0 ≤ m ≤ n
1 ≤ length of text[i] ≤ 1000
Each string text[i] is made up of characters in the range ascii[a-z].

自定义测试的输入格式 示例案例0

用于自定义测试的示例输入

STDIN功能

---

4 → n = 4 代码 → 文本 = ["代码","aaagmnrs","字谜","doce"] AAAGMNRS 字谜 多西

输出示例

aaagmnrs 代码

说明

“code”和“doce”是字谜词。删除“doce”并保留数组中第一次出现的“code”。 “aaagmnrs”和“anagrams”是字谜词。删除“anagrams”并保留数组中第一次出现的“aaagmnrs”。 按升序对剩余字符串进行排序：[“aaagmnrs”，“code”]。

def fun_with_anagrams(text: list) -> list:
    text_tuples = list(map(lambda word: ("".join(sorted(word)), word), text))
    unique_dict_of_words = {}

    for word_tuple in text_tuples:
        if word_tuple[0] not in unique_dict_of_words:
            unique_dict_of_words[word_tuple[0]] = word_tuple[1]

    words_list = list(unique_dict_of_words.values())
    return words_list


testing_texts_list = [
    ["code", "aaagmnrs", "anagrams", "doce"],
    ["listen", "silent", "enlist", "google", "gooogle"],
    ["apple", "papel", "apple", "palep", "pip"],
    ["one", "two", "three", "four", "five"],
    ["same", "same", "same", "same", "same"],
    ["a", "b", "c", "d", "e"],    ["characteristics", "catercharistis", "ricshacteristac", "charactersistic", "istcharacterrcs"],
    ["is", "si", "his", "shi", "ih"],
]

for text in testing_texts_list:
    print(fun_with_anagrams(text))

评估时间复杂度我验证这似乎是 O(m * nlogn)，是否有更好的方法来降低时间复杂度？

Answer 1

经过一番搜索，我相信这更好，因为与之前的解决方案相比，使用排序时，Counter 会降低时间复杂度。

from collections import Counter

def fun_with_anagrams_with_counter(text: list) -> list:
    unique_anagrams = {}
    result = []

    for word in text:
        counter_signature = frozenset(Counter(word).items())
        if counter_signature not in unique_anagrams:
            unique_anagrams[counter_signature] = word
            result.append(word)

    return result