What does it mean "return all groups"? But the return result is vector<string>? How can we return all groups?

Question

What does it mean "return all groups"? But the return result is vector? How can we return all groups? I mean, for example, we have such vector ["dog","cat","god","tac"]. What should I return?

Answer 1

It means return all group of anagrams being flatten into one single list.

For the input ["dog","cat","god","tac"], it should return: ["dog","cat","god","tac"], as dog and god are one group of anagrams, and cat and tac are another group of anagrams.

I will probably change the return format to a more intuitive manner sometime in the future, such as:

[
  ["dog", "god"],
  ["cat", "tac"]
]

Until this change happens, you will have to deal with the slightly confusing way of returning a flatten list, which should not affect the algorithm itself.

Comments

The output in your example looks exactly the same an input? Could you please double check an clarify? I am trying to submit my solution to this problem but I get "Output Limit Exceeded" error for my solution.

---

The order of each element in the output doesn't matter. Output limit exceeded means your code has bugs which caused the output answer to be over the allowed limit.

---

But with this error message, how would I know which test case my code failed on? It should at least log the failed test case. I've the following code and it works perfectly on all of my own test cases, but when I submit it, I get "Output Limit Exceeded" error:

public ArrayList<String> anagrams(String[] strs)
{
    HashMap<String, HashSet<String>> anagramGroups = new HashMap<String, HashSet<String>>();

    for (String s : strs)
    {
        String sig = getSignature(s);
        if (anagramGroups.containsKey(sig))
        {
            HashSet<String> group = anagramGroups.get(sig);
            if (!group.contains(s))
            {
                group.add(s);
            }
        }
        else
        {
            HashSet<String> newGroup = new HashSet<String>();
            newGroup.add(s);
            anagramGroups.put(sig, newGroup);
        }
    }

    // Flatten the groups.
    ArrayList<String> output = new ArrayList<String>();
    for (Map.Entry<String, HashSet<String>> group : anagramGroups.entrySet())
    {
        output.addAll(group.getValue());
    }

    return output;
}

private String getSignature(String s)
{
    char[] charArray = s.toCharArray();
    Arrays.sort(charArray);
    return new String(charArray);
}

---

Example:

Input: ["cat","rye","aye","dog", "god","cud","cat","old","fop","bra"]

Output: ["cat","cat","dog","god"]

---

The problem description really needs to be updated. The way you described, since order doesn't matter, I could just return the input array since every element is part of some anagram group (the group could only consist of one element).