PHP实现LeetCode 49.字母异位词分组的优化求助（无需集合数据结构）

兄弟，我来帮你搞定这个问题！你的原方案应该是用了逐个标记、两两对比的逻辑吧？这种方式不仅时间复杂度拉胯（O(n²)级别，大数据量直接卡爆），而且很容易因为异位词判断逻辑不严谨，导致像["ddddddddddg","dgggggggggg"]这种用例判断出错，完全不是最优解。

其实根本不需要什么集合，PHP的关联数组就能完美解决，核心思路就是给每个异位词生成一个唯一的“身份标识”，相同标识的字符串自动归为一组。我给你两种靠谱的实现方案，从易到难，你可以按需选：

方案一：排序生成唯一标识（简单直观） #

异位词排序后得到的字符串是完全相同的，比如"eat"和"tea"排序后都是"aet"，我们就用这个排序后的字符串作为关联数组的键，把原字符串丢到对应的键下面就行：

class Solution {
    /**
     * @param String[] $strs
     * @return String[][]
     */
    function groupAnagrams($strs) {
        $groups = [];
        foreach ($strs as $str) {
            // 拆成字符数组→排序→拼接成唯一key
            $chars = str_split($str);
            sort($chars);
            $key = implode('', $chars);
            // 自动分组
            $groups[$key][] = $str;
        }
        // 把分组结果转成要求的二维数组格式返回
        return array_values($groups);
    }
}

这个方案逻辑超清晰，你说的那两个测试用例："ddddddddddg"排序后还是自身，"dgggggggggg"排序后也是自身，两者key不同，自然会分成两个独立的组，完美解决你的第一个问题。时间复杂度是O(n*k log k)（n是字符串数量，k是单字符串最长长度），比你原来的O(n²)快了不止一个量级。

方案二：字符计数生成唯一标识（性能更优） #

如果遇到很长的字符串，排序的开销会变大，这时候可以用字符出现次数作为唯一标识——毕竟异位词的字符出现次数是完全一致的。我们用26个字母的出现次数组成一个编码字符串作为key，效率会更高：

class Solution {
    /**
     * @param String[] $strs
     * @return String[][]
     */
    function groupAnagrams($strs) {
        $groups = [];
        foreach ($strs as $str) {
            // 初始化26个字母的计数为0（对应a-z）
            $count = array_fill(0, 26, 0);
            // 遍历每个字符，统计出现次数
            for ($i = 0; $i < strlen($str); $i++) {
                // 把字符转成0-25的索引（a对应0，b对应1...）
                $index = ord($str[$i]) - ord('a');
                $count[$index]++;
            }
            // 把计数数组转成逗号分隔的字符串当key
            $key = implode(',', $count);
            $groups[$key][] = $str;
        }
        return array_values($groups);
    }
}

这个方案的时间复杂度是O(n*k)，比排序方案更快，尤其是字符串很长的时候优势明显。像你说的那两个测试用例，前者的计数key里d的次数是10、g是1，后者是d的次数1、g是10，key完全不同，分组绝对正确。

最后给你总结下原方案的问题： #

1. 用$alreadyPlaced标记+两两对比的逻辑，时间复杂度太高，大数据量直接歇菜；
2. 异位词判断逻辑如果不严谨，很容易把不同的字符串归为一组，或者把相同的拆开。

而用关联数组分组的思路，不仅逻辑简洁，性能拉满，还完全不需要依赖集合，PHP原生语法就能搞定，和Python的字典方案思路是完全一致的，只是语法写法不同而已。

备注：内容来源于stack exchange，提问作者user1729972