[Leetcode] Group Anagrams 变形词

Lin_YT 发布于2019-08-14 12:29 / 1306人阅读

摘要：我们将每个词排序后，根据这个键值，找到哈希表中相应的列表，并添加进去。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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