題目:字母異位詞分組
給你一個字符串數組,請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。
字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。
示例 1:
輸入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
輸出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
輸入: strs = [“”]
輸出: [[“”]]
示例 3:
輸入: strs = [“a”]
輸出: [[“a”]]
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 僅包含小寫字母
題目分析:當我看到這道題的時候,這道題考查的就是找出所有的包含相同字母的單詞(單詞中的字母順序是不固定的)。我有以下幾個疑惑點:
第一、怎么進行比對,
舉個例子,比如
輸入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
輸出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
那怎么拿"eat"去和strs數組中的其他值進行比對,有沒有統一的比對標準,我原先想的是先比較字符串的長度,然后再比較每個字母是否相同,這樣復雜度就一下子上去了。
最后思考的得到的解決方案是:通過先把字符串轉成數組,再進行排序,然后再轉成字符串。如果是字符包含的字母相同,則最后得到轉化之后的字符串都是一樣的,接著再進行比較,這樣復雜度降低了,邏輯更清晰了。
第二、怎么保存相同的字母的字符串
我原先的構想是先聲明一個空數組a,來存儲相同的字母的字符串,然后再聲明一個大的數組A來存儲這個a(會有很多個這樣的a數組)。這樣的話,復雜度一下就上去了。
這一步思考的得到的解決方案是使用map來進行存儲,使用轉化后得到的字符串當做map的key值,value剛開始是一個數組(這個數組的初始化值就是剛剛遍歷到的那個值)。這樣就解決了怎么保存相同的字母的字符串的問題;
那通過解決上面這兩個疑問點,也相當于解答出了這道題;
具體代碼如下:
/*** @param {string[]} strs* @return {string[][]}*/
var groupAnagrams = function(strs) {let strsMap = new Map()for (let str of strs) {// 字符串先轉化成數組,然后對數組進行排序,排序之后,再轉化為字符串。(相同字母組成的字符串最后轉為的字符串都是一樣的值)let switchStr = str.split('').sort().join('');// 這里注意split和join的用法,傳入分割的字符// 如果map中包含轉化后的字符串,則把這個str push到數組中if (strsMap.has(switchStr)) {strsMap.get(switchStr).push(str);} else {// 如果map中不包含轉化后的字符串,則用map.set設置key,value,key值為轉化之后的值,value為初始化的數組strsMap.set(switchStr, [str])}}// 輸出最后得到的數組值return Array.from(strsMap.values())
};