题目地址
https://leetcode.com/problems/group-anagrams/description/
题目描述
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
All inputs will be in lowercase.
The order of your output does not matter.
思路
一个简单的解法就是遍历数组,然后对每一项都进行排序,然后将其添加到 hashTable 中,最后输出 hashTable 中保存的值即可。
这种做法空间复杂度 O(n), 假设排序算法用的快排,那么时间复杂度为 O(n * klogk), n 为数组长度,k 为字符串的平均长度
代码:
var groupAnagrams = function(strs) { const hashTable = {}; function sort(str) { return str .split("") .sort() .join(""); } // 这个方法需要排序,因此不是很优,但是很直观,容易想到 for (let i = 0; i < strs.length; i++) { const str = strs[i]; const key = sort(str); if (!hashTable[key]) { hashTable[key] = [str]; } else { hashTable[key].push(str); } } return Object.values(hashTable); };
下面我们介绍另外一种方法,我们建立一个 26 长度的 counts 数组(如果区分大小写,我们可以建立 52 个,如果支持其他字符依次类推)。
然后我们给每一个字符一个固定的数组下标,然后我们只需要更新每个字符出现的次数。 最后形成的 counts 数组如果一致,则说明他们可以通过
交换顺序得到。这种算法空间复杂度 O(n), 时间复杂度 O(n * k), n 为数组长度,k 为字符串的平均长度.
关键点解析
- 桶排序
代码
- 语言支持: Javascript,Python3
/* * @lc app=leetcode id=49 lang=javascript * * [49] Group Anagrams */ /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function(strs) { // 类似桶排序 let counts = []; const hashTable = {}; for (let i = 0; i < strs.length; i++) { const str = strs[i]; counts = Array(26).fill(0); for (let j = 0; j < str.length; j++) { counts[str[j].charCodeAt(0) - "a".charCodeAt(0)]++; } const key = counts.join(""); if (!hashTable[key]) { hashTable[key] = [str]; } else { hashTable[key].push(str); } } return Object.values(hashTable); };
Python3 Code:
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: """ 思路同上,在Python中,这里涉及到3个知识点: 1. 使用内置的 defaultdict 字典设置默认值; 2. 内置的 ord 函数,计算ASCII值(等于chr)或Unicode值(等于unichr); 3. 列表不可哈希,不能作为字典的键,因此这里转为元组; """ str_dict = collections.defaultdict(list) for s in strs: s_key = [0] * 26 for c in s: s_key[ord(c)-ord('a')] += 1 str_dict[tuple(s_key)].append(s) return str_dict.values()LeetCode题解计算机为什么是基于二进制的?
可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈
LeetCode题解白石搭白塔输入黑块和白块的数量,用输入的方块数目建塔,输出最大高度和种数,两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同,逐层递减1,最高层为12. 每层颜色相同
LeetCode题解分鸡块外卖鸡块分别有 4,6,12 块, 每 固定块数不能分开装, 用户给一个数字, 要求返回满足用户订单(可以等于也可以大于)的最少的盒数的组合