力扣49-字母异位分组


力扣49-字母异位分组

一、原题题目

1.1 题目

  给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

1.2 示例

  • 示例1:

    输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

    输出:

    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]

说明:

  • 所有输入均为小写字母。

  • 不考虑答案输出的顺序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/group-anagrams/

二、解题思路一

2.1 题目意思理解

  这道题题目意思比较简单,即单词的字母组成上相同的但排列顺序不同的分为一个组,遍历每一个单词和保存结果lists中的每一个组中单词是不是异位的,是则加入改组,不是则判断下一组,直到遍历完存在的所有组,则创建一个新组加入。

2.2 详细代码(Java)

public class Solution {
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> lists = new ArrayList<>();       // 定义保存结果的 lists
        for (int i = 0;i<strs.length;i++){                  // 遍历每一个单词
            boolean flag = false;                           // 记录是否有加入已经存在的组
            for (List<String> list : lists) {               // 遍历lists中的每一个组
                if (isSameWords(strs[i],list.get(0)))   {   // 判断当前组的第一个单词和遍历的单词是否异位
                    list.add(strs[i]);                      // 是异位则加入该组
                    flag = true;                            // 状态改为已加入组的状态
                    continue;                               // 跳过后面的组
                }
            }
            if (flag == false) {    // 没有加入组,说明没有与任何已经存在的组异位,自己独自建组加入lists
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                lists.add(list);
            }
        }
        return lists;           // 最终返回lists
    }
    public static boolean isSameWords(String word1,String word2){   // 判断两个单词是否异位
        if (word1.length()!= word2.length())    return false;
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        return String.valueOf(chars1).equals(String.valueOf(chars2));
    }
}

2.3 算法执行结果

算法执行结果

  结果比较惨,但还好也是自己很快就相处来的方法,接着再思考思考提升下性能。

三、解题思路二(哈希表)

3.1 题目意思理解

  大概意思跟上一种思路一致,用哈希表来存储结果,每一个单词先转换成字符数组,然后排序,再把排序后的字符数组转换成字符串作为同类异位单词的 key ,组作为 value。例如示例:[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],对于 “eat” 和 “tea” 单词他们转化求 key 都是 “aet” ,即属于同一个组。

3.2 详细代码(Java)

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> hashMap = new HashMap<>();     // 定义哈希表存储分组结果
        for (int i =0 ;i<strs.length;i++){              // 遍历每一个单词
            char[] chars = strs[i].toCharArray();       // 单词转换成字符数组
            Arrays.sort(chars);                         // 对单词字符数组排序
            String key = new String(chars);             // 得到单词对应的 key 
            if (hashMap.containsKey(key)){              // 如果这个 key 在哈希表中存在 
                List<String> list = hashMap.get(key);   // 取出 key 对应的组 
                list.add(strs[i]);                      // 将该单词加入到这个组 
            }
            else {                                          // 如果这个 key 在哈希表中不存在 
                ArrayList<String> list = new ArrayList<>(); // 要新创建一个组
                list.add(strs[i]);                          // 新创建的组中加入该单词
                hashMap.put(key,list);                      // 新创建的组加入哈希表中
            }
        }
        List<List<String>> result = new ArrayList<>(hashMap.values());  // 哈希表值的部分转换成需要输出的格式
        return result;
    }
}

3.3 算法执行结果

改进算法执行结果

  这个结果还行,两种方法思路上差别还是存在很大差距的,哈希表的运用大幅度提升了性能。


文章作者: ItDaChuang
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ItDaChuang !
评论
 上一篇
力扣103-二叉树的锯齿形层序遍历 力扣103-二叉树的锯齿形层序遍历
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
2020-12-22
下一篇 
力扣746-使用最小花费爬楼梯 力扣746-使用最小花费爬楼梯
数组的每个索引作为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。
2020-12-21
  目录