LeetCode49.字母异味词分组

这篇具有很好参考价值的文章主要介绍了LeetCode49.字母异味词分组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode49.字母异味词分组,leetcode,leetcode,算法,java

 我一开始的思路就是用1个hashmap<Integer,List<String>>,Integer存的的是字符串所有字母ASCLL值的和,List里面放异位字符串,但是不是异位的字符串的ascll值也可能相同比如acd和abe,所以这个hashmap只能降低一点时间复杂度我还是要写一个方法来判断是不是异位字符串,就在我写的时候我突然意识到,这样的话hashmap的key会重复啊,我必须得想办法找到一个key使得异位字符串有相同的key其他没有。百思不得其解,最后还是点开了题解,刚点开,映入眼帘的”字母排序“四个字让我恍然大悟,我立马关掉题解自己写。

异位字符串把字母排完之后就是一样的啊,拿这个排完序的字符串作为key就好了啊,最简单的排序当然是冒泡了,但是我交换两个字母顺序的时候我写的str.charAt(i)=str.charAt(j),这行代码有问题,好像不能这样赋值,只能用双等号比较,然后就写了一个很屎的字符串排序,知道通过排序字母就知道如何解题了,以下是我的屎代码:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
          List<List<String>> ans = new ArrayList<List<String>>();
          int n = strs.length;
          HashMap<String,List<String>> map = new HashMap<>();
          for(int i=0;i<n;i++){
              String strSort = strSort(strs[i]);
              if(map.containsKey(strSort)){
                     map.get(strSort).add(strs[i]);
              }else{
                   List value = new ArrayList<String>();
                   value.add(strs[i]);
                     map.put(strSort,value);
              }
          }
          for (String key:map.keySet()) {
            ans.add(map.get(key));
        }
        return ans;
    }
    public String strSort(String str){
        int n = str.length();
        char[] c = new char[n];
        for(int i=0;i<n;i++){
            c[i] = str.charAt(i);
        }
        for(int i=0;i<n;i++){
          for(int j = i+1;j<n;j++){
              if(c[i] > c[j]){
                  char tmp = c[i];
                  c[i] = c[j];
                  c[j] = tmp;
              }
          }
        }
        String s = new String();
        for(int i=0;i<n;i++){
            s+=c[i];
        }
        return s;
    }
}

看了下题解的代码,太牛了,很简洁,他都没自己排序

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

先用toArray()方法把一个字符串变成字符串数组,然后用Arrays.sort()方法把字符串数组排序,然后通过传入一个字符串数组参数的构造方法创建这个排好了序的字符串,唉,我也是按照这三步写的,但是tmd我全是自己写的,这说明我对一些类的常用方法根本不熟悉。后面他没有进行key的判断,而是通过调用map.getOrDefault,其实原理一样,map.getOrDefault也是先看有没有这个key,有就拿出这个value,没有就返回设置的默认值,这里的默认值是新建一个list,后面就add,put。

题解还有一种不排序的方法,就是统计字母的频次,然后把频次的数字转成char加起来就是一个String,然后把这个String作为key,例如leetcode的key就是”00113000000100100001000000“,这样异位字符串的key也是相同的。文章来源地址https://www.toymoban.com/news/detail-657085.html

到了这里,关于LeetCode49.字母异味词分组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Golang | Leetcode Golang题解之第49题字母异位词分组

    题目: 题解:

    2024年04月26日
    浏览(72)
  • 【算法题】49. 字母异位词分组

    给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs = [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"] 输出: [[\\\"bat\\\"],[\\\"nat\\\",\\\"tan\\\"],[\\\"ate\\\",\\\"eat\\\",\\\"tea\\\"]] 示例 2: 输入: strs = [\\\"\\\"] 输出:

    2024年01月22日
    浏览(37)
  • leetcode热题100. 字母异位词分组

    Problem: 49. 字母异位词分组 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”

    2024年02月19日
    浏览(40)
  • 力扣每日一题49:字母异位词分组

    给你一个字符串数组,请你将  字母异位词  组合在一起。可以按任意顺序返回结果列表。 字母异位词  是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 示例 2: 示例 3: 提示: 1 = strs.length = 104 0 = strs[i].length = 100 strs[i]  仅包含小写字母 通过次数 542.1K 提交次数

    2024年02月07日
    浏览(40)
  • 力扣:49. 字母异位词分组(Python3)

    给你一个字符串数组,请你将  字母异位词  组合在一起。可以按任意顺序返回结果列表。 字母异位词  是由重新排列源单词的所有字母得到的一个新单词。 来源:力扣(LeetCode) 链接:力扣 示例 1: 输入:strs = [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"] 输出:[[\\\"bat\\\"],[\\\"nat\\\",\\\"tan\\\"],[\\\"

    2024年02月14日
    浏览(38)
  • LeetCode_贪心算法_中等_763.划分字母区间

    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。 示例 1: 输入:s = “ababcbacadefegdehijhklij” 输出

    2024年02月14日
    浏览(84)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • leetcode316. 去除重复字母(单调栈 - java)

    难度 - 中等 leetcode316. 去除重复字母 给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。 示例 1: 输入:s = “bcabc” 输出:“abc” 示例 2: 输入:s = “cbacdcbc” 输出:“acdb”

    2024年02月10日
    浏览(41)
  • 稀碎从零算法笔记Day45-LeetCode:电话号码的字母组合

    题型:映射、回溯算法、递归 链接:17. 电话号码的字母组合 - 力扣(LeetCode) 来源:LeetCode 给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例

    2024年04月11日
    浏览(42)
  • 数据结构与算法之数组: Leetcode 914. 卡牌分组 (Typescript版)

    卡牌分组 https://leetcode.cn/problems/x-of-a-kind-in-a-deck-of-cards/ 描述 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X = 2 时返回 true。

    2024年02月02日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包