-7

Fun with Anagrams Description

Two strings are anagrams if they are permutations of each other. In other words, both strings have the same size and the same characters. For example, "aaagmnrs" is an anagram of "anagrams". Given an array of strings, remove each string that is an anagram of an earlier string, then return the remaining array in sorted order.

Example

str = ['code', 'doce', 'ecod', 'framer', 'frame']

"code" and "doce" are anagrams. Remove "doce" from the array and keep the first occurrence "code" in the array. "code" and "ecod" are anagrams. Remove "ecod" from the array and keep the first occurrence "code" in the array. "code" and "framer" are not anagrams. Keep both strings in the array. "framer" and "frame" are not anagrams due to the extra 'r' in 'framer'. Keep both strings in the array. Order the remaining strings in ascending order: [ "code","frame","framer"].

Function Description

Complete the function funWithAnagrams in the editor below.

funWithAnagrams has the following parameters:

string text[n]:  an array of strings

Returns:

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

Constraints

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

Input Format For Custom Testing Sample Case 0

Sample Input For Custom Testing

STDIN Function


4 → n = 4 code → text = ["code","aaagmnrs","anagrams","doce"] aaagmnrs anagrams doce

Sample Output

aaagmnrs code

Explanation

"code" and "doce" are anagrams. Remove "doce" and keep the first occurrence "code" in the array. "aaagmnrs" and "anagrams" are anagrams. Remove "anagrams" and keep the first occurrence "aaagmnrs" in the array. Order the remaining strings in ascending order: ["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]

    result = list(unique_dict_of_words.values())
    return sorted(result)


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))

Evaluating the time complexity I verify that this seems to be O(m * nlogn), is there a better approach to reduce the time complexity?

2
  • 4
    You probably want to post this question to this site, which is for code review questions.
    – Tom Karzes
    Commented Jun 14 at 10:30
  • I would like to know why this is getting down-votings, it would really help to learn and get better. Please point other solutions, other examples, other references and not just click the bloody down button... SO is getting better and better...great community here, just great :\
    – mseromenho
    Commented Jul 12 at 16:26

2 Answers 2

0

After a bit of searching I believe this is better, since Counter will reduce the time complexity compared to the previous solution when using sorting.

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 sorted(result)
0

You could use a dictionary where the keys are the sorted version of any given word (as a tuple) and the associated value is a list of all words that sort to the same key.

Subsequently you just need to extract the first element from each value (list).

This technique removes the need to check to see if a key has already been observed.

Something like this:

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"],
]


def fun_with_anagrams(data: list[str]) -> list[str]:
    t: dict[tuple[str, ...], list[str]] = {}
    for word in data:
        k = tuple(sorted(word))
        t.setdefault(k, []).append(word)
    return sorted([v[0] for v in t.values()])

def process():
    for _list in testing_texts_list:
        print(fun_with_anagrams(_list))

if __name__ == "__main__":
    process()

Output:

['aaagmnrs', 'code']
['google', 'gooogle', 'listen']
['apple', 'pip']
['five', 'four', 'one', 'three', 'two']
['same']
['a', 'b', 'c', 'd', 'e']
['catercharistis', 'characteristics', 'istcharacterrcs']
['his', 'ih', 'is']
1
  • Thanks for the alternative @SIGHUP. Isn't the time complexity still O(m×nlogn), since you're using the sorted(word)?
    – mseromenho
    Commented Jun 16 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.