CCI习题1-4:Anagrams

By | 2012 年 11 月 13 日

第一个方法直接将输入字符串排序,然后比较。
时间复杂度是O(nlogn),空间是O(1)

第二个方法是hash,统计每个字符出现的个数。
时间复杂度是O(n),空间O(n)



Write a method to decide if two strings are anagrams or not.



代码

<

pre>

//
// main.cpp
// CCI.1.4.Anagram
//
// Created by Qiu Xiangyu on 12-11-13.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

using namespace std;

bool anagram(string &str0, string &str1) {
sort(str0.begin(),str0.end());
sort(str1.begin(),str1.end());
return str0 == str1;
}

bool anagram1(string &str0, string &str1) {
if (str0.size() != str1.size()) {
return false;
}
int map[256];
for (int i = 0; i < 256; ++i)
map[i] = 0;
for (int i = 0; i < str0.size(); ++i) {
map[str0[i]] ++;
}
for (int i = 0; i < str1.size(); ++i) {
— map[str1[i]];
}
for (int i = 0; i < 256; ++i) {
if (map[i] != 0) {
return false;
}
}
return true;
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input Str0 below:\n”;
string str0;
cin>>str0;
cout<<“Input Str0:”<<str0<<endl<<“Input Str1 below:”<<endl;
string str1;
cin>>str1;
cout<<“Input Str1:”<<str1<<endl;

//process
bool isAnagram = anagram1(str0,str1);
cout<<"Result : "<<isAnagram<<endl;

return 0;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注