#49 Group Anagrams
善用英文字母只有 26 的優勢
Given an array of strings strs, group the strings that are anagrams of each other. The result can be returned in any order.
An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.
Input
strs: string[]: An array of strings
Examples
Input: strs = ["abc","bca","cab","xyz","zyx"]
Output: [["abc","bca","cab"],["xyz","zyx"]]
Explanation: Two anagram groups: 'abc'-'bca'-'cab' and 'xyz'-'zyx'.Input: strs = ["rat","tar","art","car","arc"]
Output: [["arc","car"],["art","rat","tar"]]
Explanation: Two anagram groups: 'car'-'arc' and 'rat'-'tar'-'art'.Input: strs = ["kxac","swavb","lmq","lvhc","sjey"]
Output: [["kxac"],["lmq"],["lvhc"],["sjey"],["swavb"]]
Explanation: Each word has no anagram in the list.怎麼解
把 "abc" 用成 [1, 1, 1, 0,.....] 所以 'abc" 跟 "bca" 會是一樣的 key
注意 edge case 例如 "aab" 會是 [2, 1, 0, 0...]
/**
* @param {string[]} strs
* @return {string[][]}
*/
export default function anagramGroups(strs) {
let len = strs.length;
if (len === 0) return [];
let lookup = new Map();
let result = [];
for (let i = 0; i < len; i++) {
let key = transformFromAlphabetToCollections(strs[i]);
if (lookup.has(key)) {
lookup.set(key, [...lookup.get(key), strs[i]]);
} else {
lookup.set(key, [strs[i]]);
}
// [1,1,1,....]
}
lookup.values().forEach((val) => result.push(val));
return result;
}
// "abc"
function transformFromAlphabetToCollections(str) {
let result = Array.from({ length: 26 }, () => 0);
for (let i = 0; i < str.length; i++) {
result[str[i].charCodeAt() - 97] += 1;
}
return JSON.stringify(result);
}
Last updated
Was this helpful?