题目
解法一:
因为本人学艺不精,目前并未了解一些高端轮子的使用技巧。所以我将这题视作一道数学问题去解答。
每一个字符都会有它对应的ASCII码
比如小写字母a ~ z的ASCII码就为97 ~ 122。那么我们就可以从小学数学角度入手了。
1 | vector<vector<string>> Solution::groupAnagrams(vector<string> &strs) { |
显而易见这个算法的复杂度是O(N^2),相当的慢,是我目前知识水平能想出的解决方法了,但是在内存占用上比其他高速算法低是它仅剩的优点了。
当然,我们还能用质数去解决这个问题
解法2:
根据 质因数分解定理
我们可以推得
任一一个合数都能分解为质数的乘积
,所以我们可以得到另外一个结论
一组质数的相乘结果
是不可能由 另一组组合不同的质数相乘
得到的
知道这个结论之后,这道题也就变成了简单数学问题。
1 | vector<vector<string>> Solution::groupAnagrams(vector<string> &strs) { |
大体思路与解法1相似,只是将算术验证改为了 质数验证
优缺点也和第一题一致,速度慢,节约内存。
解法3:
利用现有的高级库去解决,比如map类
,是一个hash表。
map类是C++中的一个标准容器,它提供了很好一对一的关系
思路
使用 map 类 创建一个 string 对 string 的 容器
遍历字符串数组
创建一个临时变量储存字符串,对每一个字符串排序
将排序好的字符串作为key,原始字符串为value,压入map。
通过遍历map将容器中的每个value数组压入返回结果。
1 | vector<vector<string>> Solution::groupAnagrams(vector<string> &strs) { |
这个方法大大优化了运行效率,同时还保持着内存占用低的优点。所以现有的库能解决相当多的问题
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/16/学习笔记-Leetcode字母异位词分组/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!