注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex59 Anagrams  

2015-05-23 22:43:30|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

这一题,严格来说比较简单,就是把那些个相似的全部字典排序,如果是Anagrams的,一定排序之后是一样的,这样就是找重复的元素过程了,见c代码,排序的过程调用快排。

struct Node{
string str;
string order;
};
bool cmp(Node a,Node b)
{
return a.order > b.order;
}

/*
* 回文子串在这里的定义就是,两个字符串内字符出现的都是一样的,就是顺序可以不同
* 比如ate 和eta 还有tae 等等
* 有了这个性质就比较好做了,直接把每个字符串排序,然后相等的就是我们要找的,
* 把这些重复出现的拿出来就行了
*/
class Solution {
public:
vector<Node>array;
vector<string>result;
vector<string> anagrams(vector<string>& strs) {
int len = strs.size();
int i;
string ordered;
Node tmp;
for (i = 0; i < len; i++)
{
tmp.str = strs[i];
ordered = strs[i];
sort(ordered.begin(), ordered.end());
tmp.order = ordered;
array.push_back(tmp);
}
sort(array.begin(),array.end(),cmp);
traverse();
return result;
}
void traverse()
{
int len = array.size();
int ps = 0,pe = 0;
int count = 0;
while (ps < len)
{
count = 0;
while (((pe+1)<len )&& (array[ps].order == array[pe + 1].order))
{
if (count == 0)
{
result.push_back(array[ps].str);
}
result.push_back(array[pe+1].str);
pe++;
count++;
}
ps = pe + 1;
pe = ps;
}
}
};


  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017