Group Anagrams
49.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"]]
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.
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
Approach 1
Complexity
-
Time complexity: O(n∗k)O(n*k)O(n∗k) (K is the length of the longest string)
-
Space complexity: O(n∗k)O(n*k)O(n∗k) (K is the length of the longest string)
/**
* @param {string} s
* @return {string}
*/
var getSignature = function (s) {
const count = Array(26).fill(0)
for (const c of s) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++
}
const result = []
for (let i = 0; i < 26; i++) {
if (count[i] !== 0) {
result.push(String.fromCharCode(i + 'a'.charCodeAt(0)), count[i].toString())
}
}
return result.join('')
}
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
const result = []
const groups = new Map()
for (const s of strs) {
const signature = getSignature(s)
if (!groups.has(signature)) {
groups.set(signature, [])
}
groups.get(signature).push(s)
}
groups.forEach(value => result.push(value))
return result
}
/**
* @param {string} s
* @return {string}
*/
var getSignature = function (s) {
const count = Array(26).fill(0)
for (const c of s) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++
}
const result = []
for (let i = 0; i < 26; i++) {
if (count[i] !== 0) {
result.push(String.fromCharCode(i + 'a'.charCodeAt(0)), count[i].toString())
}
}
return result.join('')
}
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
const result = []
const groups = new Map()
for (const s of strs) {
const signature = getSignature(s)
if (!groups.has(signature)) {
groups.set(signature, [])
}
groups.get(signature).push(s)
}
groups.forEach(value => result.push(value))
return result
}
Approach 2
Complexity
-
Time complexity: O(n∗k∗logk)O(n _ k _ log k)O(n∗k∗logk) (K is the length of the longest string)
-
Space complexity: O(n∗k)O(n*k)O(n∗k) (K is the length of the longest string)
var groupAnagrams = function (strs) {
const mp = new Map()
const ans = []
for (const str of strs) {
const sortedStr = str.split('').sort().join('')
if (mp.has(sortedStr)) {
ans[mp.get(sortedStr)].push(str)
} else {
mp.set(sortedStr, ans.length)
ans.push([str])
}
}
return ans
}
var groupAnagrams = function (strs) {
const mp = new Map()
const ans = []
for (const str of strs) {
const sortedStr = str.split('').sort().join('')
if (mp.has(sortedStr)) {
ans[mp.get(sortedStr)].push(str)
} else {
mp.set(sortedStr, ans.length)
ans.push([str])
}
}
return ans
}
My code
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
const hashTable = {}
strs.forEach(str => {
const key = parseToKey(str)
if (hashTable[key]) {
hashTable[key].push(str)
} else {
hashTable[key] = [str]
}
})
return Object.values(hashTable)
}
// sort char of str
const parseToKey = str => {
for (let i = 0; i < str.length - 1; i++) {
for (let j = i + 1; j < str.length; j++) {
if (str[i] > str[j]) {
str = swapStr(str, i, j)
}
}
}
return str
}
function swapStr(str, first, last) {
return str.substr(0, first) + str[last] + str.substring(first + 1, last) + str[first] + str.substr(last + 1)
}
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
const hashTable = {}
strs.forEach(str => {
const key = parseToKey(str)
if (hashTable[key]) {
hashTable[key].push(str)
} else {
hashTable[key] = [str]
}
})
return Object.values(hashTable)
}
// sort char of str
const parseToKey = str => {
for (let i = 0; i < str.length - 1; i++) {
for (let j = i + 1; j < str.length; j++) {
if (str[i] > str[j]) {
str = swapStr(str, i, j)
}
}
}
return str
}
function swapStr(str, first, last) {
return str.substr(0, first) + str[last] + str.substring(first + 1, last) + str[first] + str.substr(last + 1)
}
Some things I learned from this problem
- String is immutable, we can't swap the char in the string like we do for array
In JavaScript, primitive values are immutable — once a primitive value is created, it cannot be changed, although the variable that holds it may be reassigned another value. By contrast, objects and arrays are mutable by default — their properties and elements can be changed without reassigning a new value.