[LeetCode] 49. Group Anagrams
題目
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.
1 < = strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lower-case English letters.
直覺解
構想：
result 的格式預計就是要回傳的答案。比對 strs 中每個字串，是否和 result 中任一元素的第一個元素，都使用一樣且數量相同的字母。比對的方式是，雙方同時刪掉某個特定字母，刪完之後雙方長度是否一樣。
javascript 實作：
const groupAnagrams = function(strs) {
if (strs.length < 2) { return [strs]}
const result = []
strs.forEach(str => {
let isGrouped = false
for (const group of result) {
let isAnagram = true
if (group[0].length !== str.length) {
isAnagram = false
continue
}
let originalLetters = group[0]
let string = str
for (let i = string.length - 1; i >= 0 ; i--) {
if (originalLetters === string) {
break
}
originalLetters = originalLetters.replace(string[i], '')
string = string.replace(string[i], '')
if (originalLetters.length !== string.length) {
isAnagram = false
break
}
}
if (isAnagram) {
group.push(str)
isGrouped = true
break
}
}
if (!isGrouped) {
result.push([str])
}
})
return result
}
效能：
Runtime: 2268 ms, faster than 5.00% of JavaScript online submissions for Group Anagrams.
Memory Usage: 48.6 MB, less than 88.76% of JavaScript online submissions for Group Anagrams.
犯過的錯誤：
- 題目寫「typically using all the original letters exactly once」，所以以為這不是題目的限制之一，於是在
strs = ["ddddddddddg","dgggggggggg"]時把這兩個字串分在同一組，結果就答錯了。 - 因為我刪除比對過的字母的方式是，把比對過的字母用空字串取代，所以
strs中有空字串時，沒辦法用「把比對過的字母用空字串取代」的方式處理。最後是當成例外狀況來處理，不過程式碼看起來就更不精簡了。 - 「把比對過的字母用空字串取代」計算起來滿花時間的，在效能上很不理想。
參考別人的解後，javascript 實作優化：
構想：紀錄 26 個字母中，每個字母出現幾次，把這個紀錄當作分組的標籤。
const groupAnagrams = function(strs) {
if (strs.length < 2) { return [strs] }
const result = []
strs.forEach(str => {
const codeOfa = 'a'.charCodeAt(0)
const map = Array.from({ length: 26 }, item => 0)
for (const index in str) {
map[str.charCodeAt(index) - codeOfa]++
}
const groupTag = map.join('-')
let isGroup = false
for (const group of result) {
if (group[0] === groupTag) {
group.push(str)
isGroup = true
break
}
}
if (!isGroup) {
result.push([groupTag, str])
}
})
for (const group of result) {
group.splice(0, 1)
}
return result
}
效能：
Runtime: 976 ms, faster than 5.00% of JavaScript online submissions for Group Anagrams.
Memory Usage: 50.9 MB, less than 22.02% of JavaScript online submissions for Group Anagrams.
犯過的錯誤：
- tag 沒有加分隔號，結果
strs = ["bdddddddddd","bbbbbbbbbbc"]時，兩者的 tag 剛好一樣。
參考別人的解後，javascript 實作優化：
構想：group 從陣列改成物件，這樣要比對分組標籤時就不需迭代陣列。簡化取得分組標籤的方式。
const groupAnagrams = function(strs) {
if (strs.length < 2) { return [strs] }
const group = {}
strs.forEach(str => {
const groupKey = str.split('').sort().join('')
if (!group[groupKey]) {
group[groupKey] = [str]
} else {
group[groupKey].push(str)
}
})
return Object.values(group)
}
效能：
Runtime: 132 ms, faster than 67.62% of JavaScript online submissions for Group Anagrams.
Memory Usage: 49.8 MB, less than 50.17% of JavaScript online submissions for Group Anagrams.
Comments
Post a Comment