[Leetcode] Group Anagrams 變形詞

Lin_YT 發布于2019-08-14 12:29 / 1327人閱讀

摘要：我們將每個詞排序后，根據這個鍵值，找到哈希表中相應的列表，并添加進去。

Group Anagrams 最新更新請見：https://yanjia.me/zh/2019/01/...

Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

排序哈希表法 復雜度

時間 O(NKlogK) 空間 O(N)

思路

判斷兩個詞是否是變形詞，最簡單的方法是將兩個詞按字母排序，看結果是否相同。這題中我們要將所有同為一個變形詞詞根的詞歸到一起，最快的方法則是用哈希表。所以這題就是結合哈希表和排序。我們將每個詞排序后，根據這個鍵值，找到哈希表中相應的列表，并添加進去。為了滿足題目字母順序的要求，我們輸出之前還要將每個列表按照內部的詞排序一下。可以直接用Java的Collections.sort()這個API。

注意

將字符串排序的技巧是先將其轉換成一個char數組，對數組排序后再轉回字符串

代碼

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())

云服務器 GPU云服務器 Anagrams LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64505.html

[LintCode] Anagrams

摘要：對變形詞的查找和歸類，可以將自然排序的詞根和所有同根變形詞成對存入哈希表里。然后，返回里大于的字符串數組，再存入結果數組。注意并不是的結構，而是和數組相同的，所以存到一定要用方法。有幾行容易出錯的語句，可以注意一下 Problem Given an array of strings, return all groups of strings that are anagrams. Not...

GitChat 2019-08-14 15:22 評論0 收藏0
leetcode 49 Group Anagrams

摘要：不需要關注輸出的順序，所有的輸入都是小寫。的就是經過排序后的字符數組所對應的字符串。因為不需要考慮輸出的順序，所以遍歷完直接輸出中的所有值即可。解法邊界情況判斷如果存在相同組成的元素題目詳情 Given an array of strings, group anagrams together.題目要求輸入一個字符串數組，我們要將由同樣字母組成的字符串整理到一起，然后以如下例子中的格式...

陳偉 2019-08-16 12:43 評論0 收藏0
leetcode49 Group Anagrams

摘要：同時使用方法將數組轉化為并利用的直接比較兩個字符串是否相等。通過這種方法效率值提高了不少。題目要求 Given an array of strings, group anagrams together. For example, given: [eat, tea, tan, ate, nat, bat], Return: [ [ate, eat,tea], [nat,t...

sunsmell 2019-08-16 10:35 評論0 收藏0
[LeetCode] Group Anagram

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 ...

kid143 2019-08-19 11:08 評論0 收藏0
[Algo] Anagram Substring Search 變形詞子串

摘要：統計字母頻率復雜度時間空間思路用一個位的數組統計字符串中每一個字符出現的次數，然后同理，維護一個長度為長度的窗口，來統計這個窗口里母串各個字符出現的次數，計入一個數組中。比較這兩個數組是否相同就知道是否是變形詞子串了。 Anagram Substring Search Given a text txt[0..n-1] and a pattern pat[0..m-1], write ...

Channe 2019-08-14 12:45 評論0 收藏0