2020-05-16-Go和PHP 实现字母异位词分组

layout: posttitle: Go和PHP 实现字母异位词分组
subtitle: Go和PHP 实现字母异位词分组
date: 2020-05-16
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 实现字母异位词分组

原文链接：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);
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券