Go和PHP 实现字母异位词分组

Go和PHP 实现字母异位词分组

author: he xiaodong date: 2020-05-16

原文链接:go lettcode,php 代码个人原创

字母异位词分组( Group-Anagrams )

题干:

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

解题思路

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

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

流程图如下:

其他标准:

    1. 题目指明字符串由小写字母组成,因此可以初始化一个长度为 26 的数组对应一个字符串,记录字符串每一个字母出现的次数。如果两个数组相同,则表示对应的字符串为一组。( 注意空间复杂度 )

    2. 将 26 个字母与质数相关联,一个字符串由其字母对应质数的乘积表示,如果两个字符串的乘积相同,那么对应字符串为一组。( 可能会溢出 )

Go 实现

func deleteDuplicates(head *ListNode) *ListNode {
    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
}

PHP 实现

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);
}