CCI习题1-1:String Contain Unique Char

By | 2012 年 11 月 13 日

CCI指《Cracking the Coding Interview》.



用一个int做为hash表,记录每个单词是否已经存在。从头到尾扫描一下string的每一个字符就可以了。
时间复杂度O(n)
空间复杂度O(1)



1.1
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

代码

<

pre>

include

using namespace std;

bool allUnique(string inputstr) {
int map = 0;//32bit
for(int i = 0; i < inputstr.size(); ++i) {
char c = inputstr[i];
int hashc = c – ‘a’;
int bit = 1 << hashc;
if (map & bit) {
return false;
} else {
map = map | bit;
}
}
return true;
}

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

//process
bool allunique = allUnique(inputstr);
cout<<"Result : "<<allunique<<endl;

return 0;

}

发表评论

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