• 力扣每日一题49:字母异位词分组


    题目描述:

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

    字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

    示例 1:

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

    示例 2:

    输入: strs = [""]
    输出: [[""]]
    

    示例 3:

    输入: strs = ["a"]
    输出: [["a"]]

    提示:

    • 1 <= strs.length <= 104
    • 0 <= strs[i].length <= 100
    • strs[i] 仅包含小写字母

    通过次数

    542.1K

    提交次数

    799.9K

    通过率

    67.8%

    思路和题解:

    字母异位词里面的的字母都是相同的,只是排列顺序不同,如果我们把每个单词都排序一遍,排序后字母异位词是相等的,然后再将字符串数组排序一边,此时字母异位词就挨在一起了,我们只要把连在一起并且排序后相等的两个字母放进一个组合里,最后把所有的组合返回即可。听不懂的话我举个例子,就拿样例一来说strs=["eat","tea","tan","ate","nat","bat"],把每个单词排序得到a=[aet, aet ,ant ,aet ,ant ,abt],再将字符串数组a排序,排序的时候连带strs一起交换得到strs=[bat tea ate eat nat tan]   a=[abt aet aet aet ant ant] ,即

    1. 第一次将每个单词排序
    2. strs=[eat tea tan ate nat bat]
    3. a=[aet aet ant aet ant abt]
    4. 第二次将a中单词作为一个整体排序
    5. strs=[bat tea ate eat nat tan]
    6. a=[abt aet aet aet ant ant]

    来看我的代码:

    1. class Solution {
    2. public:
    3. vector> groupAnagrams(vector& strs) {
    4. vector> ans;
    5. vector a;
    6. int n=strs.size();
    7. for(int i=0;i
    8. {//先对原始字符串数组中每一个字符串进行排序
    9. a.push_back(strs[i]);
    10. sort(a[i].begin(),a[i].end());
    11. }
    12. // //test1
    13. // for(int i=0;i
    14. // cout<
    15. // cout<
    16. // for(int i=0;i
    17. // cout<
    18. // cout<
    19. // 再对字符串数组a排序,strs跟着换
    20. for(int i=0;i-1;i++)
    21. {
    22. int k=i;
    23. for(int j=i+1;j
    24. {
    25. if(a[j]
    26. }
    27. string temp=a[i];
    28. a[i]=a[k],a[k]=temp;
    29. temp=strs[i],strs[i]=strs[k],strs[k]=temp;
    30. }
    31. // //test2
    32. // for(int i=0;i
    33. // cout<
    34. // cout<
    35. // for(int i=0;i
    36. // cout<
    37. // cout<
    38. //这个时候字母异位词就黏在一起了
    39. int pos=0,i=0;
    40. while(pos
    41. {
    42. vector group;
    43. group.emplace_back(strs[pos]);
    44. while(pos-1&&a[pos]==a[pos+1])
    45. {
    46. pos++;
    47. group.emplace_back(strs[pos]);
    48. }
    49. pos++;
    50. ans.emplace_back(group);
    51. }
    52. return ans;
    53. }
    54. };

    改进:

    上述方法的核心是将所有的字母异位词放在一起(指位置相邻),然后再将相邻且排序后相等的字符串放在一个字符串数组里。其实将排序后的一个string作为键,对应的排序之前的string作为值放入一个map里,我们就可以直接把所有的字母异位词放在一起(不仅仅是字母异位词不是相邻,而且非字母异位词之前也分开了)。看代码:

    1. class Solution {
    2. public:
    3. vector> groupAnagrams(vector& strs) {
    4. vector> ans;
    5. map> mp;
    6. int n=strs.size();
    7. for(int i=0;i
    8. {
    9. string key=strs[i];
    10. sort(key.begin(),key.end());
    11. mp[key].emplace_back(strs[i]);
    12. }
    13. for(auto it=mp.begin();it!=mp.end();it++)
    14. {
    15. ans.emplace_back(it->second);
    16. }
    17. return ans;
    18. }
    19. };

    运行:

  • 相关阅读:
    SpringMVC之综合案例:参数传递,向页面传参,页面跳转
    【仿牛客网笔记】项目进阶,构建安全高效的企业服务——置顶、加精、删除
    【工作篇】软件工程师的知识基础(持续更新)
    嵌入式实时操作系统的设计与开发(互斥量学习)
    现代农业信息技术
    类和对象(前)
    php字符串的截取方式
    Python数据分析实战-表连接-merge四种连接方式用法(附源码和实现效果)
    5G通信与蜂窝模组之间的关系
    ChatGPT 帮你写作
  • 原文地址:https://blog.csdn.net/m0_73441691/article/details/133959202