Lintcode--003(乱序字符串)

时间:2023-01-03 15:20:25

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

注意事项

所有的字符串都只包含小写字母

 
样例

对于字符串数组 ["lint","intl","inlt","code"]

返回 ["lint","inlt","intl"]

标签

第一次尝试解决,方法复杂,且不能通过。代码如下:

class Solution {
public:
/**
* @param strs: A list of strings
* @return: A list of strings
*/
vector<string> anagrams(vector<string> &strs) {//vector<string> s; //定义个一个字符串容器s
// write your code here //先考虑边界情况,如果字符串数组s中的所有字符串,都不等长,则不存在乱序字符串;
for(int i=;i<strs.size();i++){
int a[i]=strs[i].size();
}
for(int j=;j<strs.size()-;j++){
for(int k=j+;k<strs.size();k++){
if(a[j]>&&a[k]>&&a[j]==a[k]){
vector<string> s;
s.push_back(strs[j]);
strs[j]=" ";
s.push_back(strs[k]);
}
else{
return null;
}
}
}
int letters[s.size()][];
memset(letters,,letters);
for (int m=;m<s.size();m++){
string ll;
ll=s[i];
for(n=;n<ll.size();n++){
letters[m][ll[n]-'a']++;
}
} vector<string> t;
for (int a=;a<s.size()-;a++){
for(int b=a+;b<s.size();b++){
for(int c=;c<;){
if (letters[a][c]==letters[b][c])
{
c=c+;
}
else{
continue;
}
}
t.push_back(s[a]);
s[a]=" ";
t.push_back(s[b]);
}
return t;
}
};

二次参考:http://blog.csdn.net/wangyuquanliuli/article/details/45792029

解决思路很简单:对每个字符串进行排序,然后用hash表记录个数就行

class Solution {
public:
/**
* @param strs: A list of strings
* @return: A list of strings
*/
vector<string> anagrams(vector<string> &strs) {//vector<string> s; 定义个一个字符串容器s
// write your code here
//分析:对每个字符串进行排序,然后用hash表记录个数就行 map<string,int> m; //定义一个关联容器(hash表),提供一对一的数据处理能力。初始值为0;
for(auto s:strs) //s与strs[i]属于同种类型,也就是说,都是字符串,从第一个字符串到最后一个字符串;
{
sort(s.begin(),s.end()); //对字符串数组中的每个字符串进行排序
m[s]++; //将排序后的s,他的值加1,但这个排序不影响strs本身,只作用于for里面。
}
vector<string> ret; //定义一个字符串容器
for(auto s:strs)
{
auto temp = s;
sort(temp.begin(),temp.end()); //将每个字符串排序,如果排序之后,发现最后的m[temp]值大于1,则说明是乱序。
if(m[temp]>)
ret.push_back(s); //把乱序的字符串放到容器中,这样遍历每个字符串,就可以得到最终的结果。
}
return ret;
}
};

1. 关于字符串容器的定义和操作:

vector<string> vec;//定义个一个字符串容器,相当于字符串数组;
string str;
str = "abc";
vec.push_back(str);//把字符串str压进容器,必须使用push_back()动态添加新元素
vec.push_back("def");//把字符串"def"压进容器
vec.push_back("123");
for(int i=0; i<vec.size(); i++)
{
cout<<vec[i]<<endl;//打印容器的内容
}
vec.pop_back();//取出容器中最后一个
for(int i=0; i<vec.size(); i++)
{
cout<<vec[i]<<endl;//打印容器的内容
}

若要一次性初始化,如下:

vec.resize(4,"abc"); //一次性有4个abc

2. 字符串相关:

【s.size()函数返回字符串s中的字符个数;s.empty()用来确认字符串s是否为空;】

【string类型拼接符"+"必须与一个string类型相邻 ,不能在两侧都是字符串常量】

注:关于hash表与HashMap原理,区别以及实现在面试中频繁出现,需要深刻理解。

3. hash表原理参考 (1). http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html

(2). http://blog.chinaunix.net/uid-24951403-id-2212565.html

(3). http://kb.cnblogs.com/page/189480/

4. HashMap原理参考 (1). http://blog.csdn.net/vking_wang/article/details/14166593#t0

(2). http://my.oschina.net/boxizen/blog/177744

Map的详细用法:   http://blog.csdn.net/sunshinewave/article/details/8067862