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;
}
new string()
aroundstrs[i].ToCharArray()
. EDIT: why even use.ToCharArray()
? \$\endgroup\$