LeetCode49 - 字母异构组词算法练习系列

这是我参与8月更文挑战的第20天，活动详情查看：8月更文挑战

前言

今天的算法练习题是字母异位词分组，什么是异位词呢？异位词就是两个单词不同，但组成的单词的字母是完全相同的，就比如aet，eat，tae，这就是字母异位词，话不多说，开搞

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

 

示例 1:

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

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

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

解题思路

• 首先看题目可知这是一道字符串组成的数组题，直接下手根本做不了，这时我们考虑用字母的ascii来解题，同时现在有两种解法，一种是根据ascii给每个单词排序（例如：eat,ate,tae,通过ascii排序得到的都是aet），然后比较排序后的单词是否相同，如相同就符合题目要求，放到同一个数组中
• 除了上面的方法还有一种更好的方法，那就是用一个有26项，每项都为0的数组来代表26个字母，然后通过ascii-97和数组中的项匹配，把这一项的值++，然后把这个26项的数组当做key存入map中
• 对map进行判断，如果map中存在key，那么就把这个项存入这个key对应的value中，反之直接存入一个新key和一个空的数组，代码入戏

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    if(strs.length ===0){ //首先，如果输入的是空数组，直接返回[]
        return []
    }
     const map = new Map() //声明一个map，用来存放比较之后的结果
    for (const str of strs){
        const characters = Array(26).fill(0) // 生成一个一共26项，每项为0的数组
        for(let i=0;i<str.length;i++){
            let ascii = str.charCodeAt(i)-97 //字母的ascii-97，刚好和下标一一对应
            characters[ascii]++
        }
        const key = characters.join(',') //把得到的数组转成字符串，当做key存入map中
        if(map.has(key)){ //如果map中已经存在这个key，则进行如下操作
            map.set(key,[...map.get(key),str])
        }else{ //如果map中不存在这个key，则进行如下操作
            map.set(key,[str])
        }
    }
    const result =[]
    for(let arr of map){ //循环取出map中的value插入数组即为我们所求结果
        result.push(arr[1])
    }
    return result
};

LeetCode运行结果

总结

本题的核心思路是通过每个输入单词的字母的ascii码来进行比较，得到一个ascii码组成的数组，然后通过比较数组得到我们想要的结果。