当前位置: 面试刷题>> 字母异位词分组(经典算法150题)


题目描述

字母异位词分组

给定一个字符串数组,将数组中的字符串按照字母异位词(即字母相同,但顺序不同的字符串)进行分组。字母异位词是指那些字母完全相同但顺序可能不同的字符串。

示例

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]

输出:

[
  ["eat","tea","ate"],
  ["tan","nat"],
  ["bat"]
]

思路

为了解决这个问题,我们可以利用哈希表(在PHP中为数组,Python和JavaScript中为对象或Map)来存储每个字符串的字母排序后作为键,而对应的值则是一个数组,用于存储所有该键对应的字母异位词。

示例代码

PHP 示例

function groupAnagrams($strs) {
    $result = [];
    
    foreach ($strs as $str) {
        $sortedStr = str_split($str);
        sort($sortedStr);
        $sortedStr = implode('', $sortedStr);
        
        if (!isset($result[$sortedStr])) {
            $result[$sortedStr] = [];
        }
        
        $result[$sortedStr][] = $str;
    }
    
    // 将结果转换为题目要求的格式
    return array_values($result);
}

// 示例用法
$input = ["eat", "tea", "tan", "ate", "nat", "bat"];
$output = groupAnagrams($input);
print_r($output);

Python 示例

def groupAnagrams(strs):
    result = {}
    
    for str in strs:
        sorted_str = ''.join(sorted(str))
        if sorted_str not in result:
            result[sorted_str] = []
        
        result[sorted_str].append(str)
    
    # 转换为列表形式
    return [result[key] for key in result]

# 示例用法
input_strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
output = groupAnagrams(input_strs)
print(output)

JavaScript 示例

function groupAnagrams(strs) {
    const result = {};
    
    for (let str of strs) {
        const sortedStr = str.split('').sort().join('');
        if (!result[sortedStr]) {
            result[sortedStr] = [];
        }
        
        result[sortedStr].push(str);
    }
    
    // 转换为数组
    return Object.values(result);
}

// 示例用法
const inputStrs = ["eat", "tea", "tan", "ate", "nat", "bat"];
const output = groupAnagrams(inputStrs);
console.log(output);

以上示例代码展示了如何在PHP、Python和JavaScript中实现字母异位词的分组。每个示例都首先通过排序字符串中的字符来生成一个键,然后使用这个键在哈希表中查找或存储对应的字母异位词列表。最后,根据需要将哈希表的值转换为题目要求的输出格式。

推荐面试题