3
\$\begingroup\$

I wrote this code in c#. It is a question from LeetCode, number 49. Given an array of strings, group the anagrams.

The examples it gives are:

["eat","tea","tan","ate","nat","bat"]

then return:

[["bat"],["nat","tan"],["ate","eat","tea"]]

I am wondering what exactly my time complexity is? I believe it is O(2n) which becomes O(n) after dropping the constant. But I am also thinking it might actually be O(2n^2) or O(n^2) because in my first for loop I have Array.Sort(new string(temp)) which may increase the time complexity. Please let me know.

Overall, how can I improve and speed up my code? Maybe I could get rid of the dictionary? Get rid of Array.Sort(new string(temp))? Create one instance of new string(temp) and use the variable instead? I am also thinking I should move everything into one for loop. How could this best be accomplished?

public IList<IList<string>> GroupAnagrams(string[] strs)
{
    IList<IList<string>> ans = new List<IList<string>>();

    Dictionary<string, List<string>> values = new Dictionary<string, List<string>>();

    for (int i = 0; i < strs.Length; i++){
        char[] temp = strs[i].ToCharArray();
        Array.Sort(new string(temp));
        if (!values.ContainsKey(new string(temp)))
            values.Add(new string(temp), new List<string> { strs[i] });
        else
            values[new string(temp)].Add(strs[i]);
    }

    for (int i = 0; i < values.Count; i++){
        ans.Add(values.ElementAt(i).Value);
    return ans;
 }
\$\endgroup\$
3
  • \$\begingroup\$ Array.Sort(new string(temp)); -> Impossible to convert from "string" to "System.Array". \$\endgroup\$ Sep 13, 2021 at 6:20
  • \$\begingroup\$ generally, (standard) sorting algorithms have n*log n complexity. So it would be n * (n * log n) + n, which is O(n^2 * log n) \$\endgroup\$
    – lukstru
    Jun 10, 2022 at 10:35
  • \$\begingroup\$ also it looks like you don't really need temp as a char array, so you could wrap the new string() around strs[i].ToCharArray(). EDIT: why even use .ToCharArray()? \$\endgroup\$
    – lukstru
    Jun 10, 2022 at 10:38

1 Answer 1

1
\$\begingroup\$

Here is my 4 lines long alternative:

var anagrams = from word in words
    let pair = new { Original = word, AlphabeticallyOrdered = string.Concat(word.OrderBy(@char => @char)) }
    group pair by pair.AlphabeticallyOrdered into anagram
    select anagram.Select(@group => @group.Original);

Here are my line by line explanations:

  1. Iterate through the received words
  2. Create a new string pair where we store the original word and the alphabetically ordered version
  3. Group them based on the alphabetically ordered version
  4. Retrieve them based on the original version

If I iterate the result like this:

foreach(var anagram in anagrams)
{
    Console.WriteLine(string.Join(",", anagram));
}

the output will look like that:

eat,tea,ate
tan,nat
bat
\$\endgroup\$

Your Answer

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

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