資訊專欄INFORMATION COLUMN
摘要：我們將每個(gè)詞排序后，根據(jù)這個(gè)鍵值，找到哈希表中相應(yīng)的列表，并添加進(jìn)去。
Group Anagrams 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/...
排序哈希表法 復(fù)雜度Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
時(shí)間 O(NKlogK) 空間 O(N)
思路判斷兩個(gè)詞是否是變形詞，最簡(jiǎn)單的方法是將兩個(gè)詞按字母排序，看結(jié)果是否相同。這題中我們要將所有同為一個(gè)變形詞詞根的詞歸到一起，最快的方法則是用哈希表。所以這題就是結(jié)合哈希表和排序。我們將每個(gè)詞排序后，根據(jù)這個(gè)鍵值，找到哈希表中相應(yīng)的列表，并添加進(jìn)去。為了滿足題目字母順序的要求，我們輸出之前還要將每個(gè)列表按照內(nèi)部的詞排序一下?？梢灾苯佑肑ava的Collections.sort()這個(gè)API。
注意將字符串排序的技巧是先將其轉(zhuǎn)換成一個(gè)char數(shù)組，對(duì)數(shù)組排序后再轉(zhuǎn)回字符串
代碼public class Solution {
public List> groupAnagrams(String[] strs) {
Map> map = new HashMap>();
for(String str : strs){
// 將單詞按字母排序
char[] carr = str.toCharArray();
Arrays.sort(carr);
String key = new String(carr);
List list = map.get(key);
if(list == null){
list = new ArrayList();
}
list.add(str);
map.put(key, list);
}
List> res = new ArrayList>();
// 將列表按單詞排序
for(String key : map.keySet()){
List curr = map.get(key);
Collections.sort(curr);
res.add(curr);
}
return res;
}
}
2018/2
class Solution:
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
anagrams = {}
for word in strs:
sortedWord = "".join(sorted(word))
if sortedWord in anagrams:
anagrams[sortedWord].append(word)
else:
anagrams[sortedWord] = [word]
return list(anagrams.values())
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64505.html
摘要：對(duì)變形詞的查找和歸類，可以將自然排序的詞根和所有同根變形詞成對(duì)存入哈希表里。然后，返回里大于的字符串?dāng)?shù)組，再存入結(jié)果數(shù)組。注意并不是的結(jié)構(gòu)，而是和數(shù)組相同的，所以存到一定要用方法。有幾行容易出錯(cuò)的語(yǔ)句，可以注意一下 Problem Given an array of strings, return all groups of strings that are anagrams. Not...
摘要：不需要關(guān)注輸出的順序，所有的輸入都是小寫。的就是經(jīng)過(guò)排序后的字符數(shù)組所對(duì)應(yīng)的字符串。因?yàn)椴恍枰紤]輸出的順序，所以遍歷完直接輸出中的所有值即可。解法邊界情況判斷如果存在相同組成的元素 題目詳情 Given an array of strings, group anagrams together.題目要求輸入一個(gè)字符串?dāng)?shù)組，我們要將由同樣字母組成的字符串整理到一起，然后以如下例子中的格式...
摘要：同時(shí)使用方法將數(shù)組轉(zhuǎn)化為并利用的直接比較兩個(gè)字符串是否相等。通過(guò)這種方法效率值提高了不少。 題目要求 Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat], Return: [ [ate, eat,tea], [nat,t...
Problem Given an array of strings, group anagrams together. Example: Input: [eat, tea, tan, ate, nat, bat], Output: [ [ate,eat,tea], [nat,tan], [bat] ] Note: All inputs will be in lowercase.The ...
摘要：統(tǒng)計(jì)字母頻率復(fù)雜度時(shí)間空間思路用一個(gè)位的數(shù)組統(tǒng)計(jì)字符串中每一個(gè)字符出現(xiàn)的次數(shù)，然后同理，維護(hù)一個(gè)長(zhǎng)度為長(zhǎng)度的窗口，來(lái)統(tǒng)計(jì)這個(gè)窗口里母串各個(gè)字符出現(xiàn)的次數(shù)，計(jì)入一個(gè)數(shù)組中。比較這兩個(gè)數(shù)組是否相同就知道是否是變形詞子串了。 Anagram Substring Search Given a text txt[0..n-1] and a pattern pat[0..m-1], write ...
閱讀 1391·2023-04-25 16:45
閱讀 1929·2021-11-17 09:33
閱讀 2321·2021-09-27 14:04
閱讀 922·2019-08-30 15:44
閱讀 2642·2019-08-30 14:24
閱讀 3425·2019-08-30 13:59
閱讀 1700·2019-08-29 17:00
閱讀 899·2019-08-29 15:33
