Daily Leet Code Challenge (Day 17) #49 Group Anagrams
Difficulty | Medium
Challenge
Given an array of strings strs
, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]
consists of lowercase English letters.
Thought process
Create a getKey()
method which takes a string as an argument and returns a serialized representation of the character count of the string. The count_chars()
function is used to count the number of occurrences of each character in the string, and the resulting array is serialized using the serialize()
function. The commented-out line shows an alternative implementation that returns an MD5 hash of the serialized character count instead of the serialized character count itself.
The groupAnagrams()
method takes an array of strings as an argument and returns an array of arrays, where each inner array contains a group of anagrams. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
The method iterates over each string in the input array and uses the getKey()
method to generate a key for each string. This key is based on the character count of the string, so all anagrams will have the same key. The method then uses this key to group all anagrams together in the $result
array.
For example, if the input array is ["eat", "tea", "tan", "ate", "nat", "bat"]
, the groupAnagrams()
method will return [["eat","tea","ate"],["tan","nat"],["bat"]]
, where each inner array contains a group of anagrams.
Solution
class Solution {
/**
* @param String[] $strs
* @return String[][]
*/
function getKey($string){
// return md5(serialize(count_chars($string, 1)));
return (serialize(count_chars($string, 1)));
}
function groupAnagrams($strs) {
$result = [];
foreach($strs as $string){
$key = $this->getKey($string);
if(array_key_exists($key, $result)){
$result[$key][]= $string;
}else{
$result[$key] = [$string];
}
}
return $result;
}
}