(LeetCode 49)Anagrams
LeetCode 49
2023-09-14 09:00:36 时间
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
题目:
给一组字符串,返回所有满足Anagrams(回文构词法)的字符串;
Anagrams是指由颠倒字母顺序组成的单词,比如“dormitory”颠倒字母顺序会变成“dirty room”,“tea”会变成“eat”。
回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。
思路:
满足Anagrams的字符串中的字符种类和数目都一样,如果对字符串排序,那么他们必定是相等,于是可以想到通过Hash表来判断该字符串是否出现过,如果出现过,即满足Anagrams;
需要考虑的是出现三个或三个以上的判断条件,这时数组式的hash表已无法满足,因此可以采用map<string,int>,通过key-value的形式来记录;
当string没有出现过,则对应的value为字符串数组的下表i,即map[string]=i;
当string已出现过一次,则对应的value可以设为-1,并输出该对应的字符串,即map[string]=-1;
当string出现过一次以上,即map[string]==-1,则直接输出该s对应的字符串;
代码:
class Solution { public: vector<string> anagrams(vector<string>& strs) { vector<string> result; int len=strs.size(); if(len<2) return result; map<string,int> anagrams; string aStr; for(int i=0;i<len;i++){ aStr=strs[i]; sort(aStr.begin(),aStr.end()); if(anagrams.find(aStr)==anagrams.end()) anagrams[aStr]=i; else{ if(anagrams[aStr]>=0){ result.push_back(strs[anagrams[aStr]]); anagrams[aStr]=-1; } result.push_back(strs[i]); } } } };
相关文章
- Java实现 LeetCode 821 字符的最短距离(暴力)
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java实现 LeetCode 463 岛屿的周长
- Java实现 LeetCode 344 反转字符串
- Java实现 LeetCode 198 打家劫舍
- Java实现 LeetCode 56 合并区间
- Java实现 LeetCode 51 N皇后
- Java实现 LeetCode 49 字母异位词分组
- Java实现LeetCode 139 单词拆分
- 【哈希表】LeetCode 49. 字母异位词分组【中等】
- LeetCode(36): 有效的数独
- Python 刷Leetcode题库,顺带学英语单词(18)
- leetcode 1438. 绝对差不超过限制的最长连续子数组----双指针篇3,滑动窗口篇2
- 【LeetCode Python实现】49. 字母异位词分组(中等)
- Leetcode 884. 两句话中的不常见单词
- 【Leetcode】Length of Last Word
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色