Facebook
Uber
Leetcode
GeeksForGeeks
Youtube
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Test Cases
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
* There is no string in strs that can be rearranged to form `"bat"`.
* The strings `"nat"` and `"tan"` are anagrams as they can be rearranged to form each other.
* The strings `"ate"`, `"eat"`, and `"tea"` are anagrams as they can be rearranged to form each other.
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 10<sup>4</sup>0 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Solution
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
if (strs == null || strs.length == 0) {
return result;
}
if (strs.length == 1) {
result.add(Arrays.asList(strs));
return result;
}
HashMap<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
String signature = getSignature(s);
groups.putIfAbsent(signature, new ArrayList<>());
groups.get(signature).add(s);
}
return new ArrayList<>(groups.values());
}
private String getSignature(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (count[i] != 0) {
sb.append((char) ('a' + i)).append(count[i]);
}
}
return sb.toString();
}
}class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
def signature(str):
count = [0]*26
for c in str:
count[ord(c) - ord('a')]+= 1
sign = []
for i in range(26):
c = (chr)(i + ord('a'))
if count[i] != 0:
sign.append(f"${c}${count[i]}")
return ''.join(sign)
groups = dict()
for string in strs:
sign = signature(string)
if sign in groups:
groups[sign].append(string)
else:
groups[sign] = [string]
print(groups)
res = []
for value in groups.values():
res.append(value)
return res