让我们一起啃算法----字母异位词分组

三斤和他的喵的个人博客 / 77 / 2 / 创建于 3年前 / 更新于 3年前

字母异位词分组（ Group-Anagrams ）

题干：

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
  输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
  输出:
  [
    [“ate”,”eat”,”tea”],
    [“nat”,”tan”],
    [“bat”]
  ]
说明：
  所有输入均为小写字母。
  不考虑答案输出的顺序。

解题思路

在现实生活中如果我们要对某些事物进行分组，首先会制定一个标准。例如以前读书的时候，一门课掌握地好坏的标准往往是考试成绩，成绩在85分以上为优秀，70以上为中等偏上，60分以上为中等，小于60分为不及格。同理，针对本题我们首先需要制定一个分组标准，标准不同，解题思路也不同。

这里提供一个常见的标准：由于字母异位词指字母相同，排列顺序不同的字符串。因此我们可以对每一个字符串的字母进行升序（降序），如果升序之后的字符串相等，那么它们就是一组的。

流程图如下：

其他标准：
1.题目指明字符串由小写字母组成，因此可以初始化一个长度为 26 的数组对应一个字符串，记录字符串每一个字母出现的次数。如果两个数组相同，则表示对应的字符串为一组。（注意空间复杂度）
2.将 26 个字母与质数相关联，一个字符串由其字母对应质数的乘积表示，如果两个字符串的乘积相同，那么对应字符串为一组。（可能会溢出）

代码实现

GO语言实现

func groupAnagrams(strs []string) [][]string {
    var res [][]string
    // 映射关系
    hashMap := make(map[string][]string)
    for _, v := range strs {
        // 转成字符数组
        charArr := []byte(v)
        // 按从小到大排序字符数组
        sort.SliceStable(charArr, func(i, j int) bool {
            return charArr[i] < charArr[j]
        })
        // 将升序排列的字符数组转成字符串，作为 map 的键
        // map 的值为分组之后的字符串，用一个数组保存（ go 切片）
        hashMap[string(charArr)] = append(hashMap[string(charArr)], v)
    }

    // 根据 map 的值生成一个二维数组（go 二维切片）
    for _, v := range hashMap {
        res = append(res, v)
    }
    return res
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a…

算法数觉结构 leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

3 人点赞

我们将带你从零开发一个项目并部署到线上，本课程教授 Web 开发中专业、实用的技能，如 Git 工作流、Laravel Mix 前端工作流等。

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

推荐文章：

更多推荐...

面试 POPER 的后端开发工程师的离奇经历 35 / 104 |

分享创造

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 47 / 16 |

博客

使用UML类图查看laravel结构，简直缩短了我看框架的时间啊，记录下，嘻嘻嘻 19 / 15 |

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

强一致性的分布式事务几种模式对比（php有了新方案） 33 / 20 |

博客

感觉PHP-FPM进程数不够？ 47 / 25 |

讨论数量: 2

yzh52521

33 声望

function groupAnagrams($strs) {
        $map = [];
        for ($i = 0; $i < count($strs); $i++) {
            $arr = str_split($strs[$i]);
            sort($arr);
            $sorted_str = implode(',', $arr);
            $map[$sorted_str][] = $strs[$i];
        }

        return array_values($map);
    }

3年前评论

三斤和他的喵（楼主）

优秀 :+1:

取名字好烦。

0 声望

mark

3年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

让我们一起啃算法----字母异位词分组

字母异位词分组（ Group-Anagrams ）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

让我们一起啃算法----字母异位词分组

字母异位词分组（ Group-Anagrams ）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录