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?