Anagrams(hash表)
2024-08-30 04:31:34
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
1.概念,首先简单介绍一下Anagram(回文构词法)。
Anagrams是指由颠倒字母顺序组成的单词,比如“dormitory”颠倒字母顺序会变成“dirty room”,“tea”会变成“eat”。
回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。
For example:
Input: ["tea","and","ate","eat","den"]
Output: ["tea","ate","eat"]
2.代码,其实就是把每个字符给排序,然后去和hash表存储的比较,时间复杂度O(n*mlogm),m为字符串容器中最大字符串的长度:
class Solution{
public:
vector<string> anagrams(vector<string> &strs) {
vector<string> res;
if(strs.size()==)
return res;
map<string,int> m;
for (int i=;i<strs.size();++i)
{
string s=strs[i];
sort(s.begin(),s.end());
if(m.count(s)==){
m[s]=i;
}else{
res.push_back(strs[i]);
if(m[s]!=-){res.push_back(strs[m[s]]);m[s]=-;}
}
}
return res;
}
};
最新文章
- 大数据系列(2)——Hadoop集群坏境CentOS安装
- HttpClient中转上传文件
- HTML5新增的属性
- JS(去掉前后空格或去掉所有空格)的用法 推荐使用jquery 方法
- [学习嵌入式开发板]iTOP-4412实现NFS网络文件系统
- Android(java)学习笔记114:LayoutInflater和findViewById
- Bzoj 3809: Gty的二逼妹子序列 莫队,分块
- Windows开发中一些常用的辅助工具
- 如何在android上去控制开发进度
- Springboot启动源码详解
- 配置多个git账号的ssh密钥
- 创作型---原型模式(C# ICloneable接口的实现)
- Mybatis自动生成,针对字段类型为text等会默认产生XXXXWithBlobs的方法问题
- 529. Minesweeper扫雷游戏
- Linux网络参数和ifconfig
- Mvvm Light 无法添加MvvmView(Win81)的问题
- [转发]将Delphi的对象方法设为回调函数
- TClientDataSet的 AddIndex
- Mac下运行git报错";xcrun: error: invalid active developer path ..";
- redis常见数据操作
热门文章
- casting in C++
- 网新恩普(T 面试)
- 浅谈nodejs与npm
- Perl语言入门: 斜线不是元字符,所以在不作为分隔符时不需要加上反斜线。
- python之操作excel:xlrd、xlwt、xlutiles、枚举函数enumerate()
- &#231;7—UIViewController
- [LUOGU] P3871 [TJOI2010]中位数
- <;Spring Cloud>;入门五 hystrix
- AES/DES 可逆性加密算法 -- java工具类
- Canal使用报错解决办法