再来一个拍拍：
////////////////////////////////////////////////////////////////////////////
////////
// Problem 1.1:
// Analysis and points:
// 1. strig operation(scan)
// 2. How to determine whether it's duplicate string?
// Method 1: using one hashtable, if it's already in
hashtable,
// it's duplicate, otherwise add into hashtable.
Complexity O(n)
// Method 2: for each characer, check whether it's duplicated
// in the left character. Complexity O(n^2)
// 3. Bonus: How to write unit test
//
////////////////////////////////////////////////////////////////////////////
////////
#include
#include // pair
#include
#include
using namespace std;
enum { ASCII_NUMBER = 256 };
/////////////////////////////////////////////////////////////////////////////
// Implement an algorithm to determine if a string has all unique characters.
// Method 1: HashTable
// Input: str - the string to be checked.
// Return: return true if it contains duplicate character.
/////////////////////////////////////////////////////////////////////////////
bool ContainsDuplicateChar(const string str)
{
bool ret = false;
// define hashTable and initilize to false. Assume it's using ascii.
bool hashTable[ASCII_NUMBER] = {false};
// scan the string and maintain the hashTable.
for (int i=0;i{
if (hashTable[str[i]] == false){
hashTable[str[i]] = true;
}else{
// this character has appeared before, return directly.
return true;
}
}
return false;
}
/////////////////////////////////////////////////////////////////////////////
// Implement an algorithm to determine if a string has all unique characters.
// Method 2: not use additional data structures
// Input: str - the string to be checked.
// Return: return true if it contains duplicate character.
/////////////////////////////////////////////////////////////////////////////
bool ContainsDuplicateCharNoExtraBuffer(const string str)
{
for (int i = 0; ifor (int j = i+1; j{
if (str[i] == str[j]) return true;
}
return false;
}
void doTest(bool (* ContainsDuplicateCharFunc)(const string str), vector<
pair > &TestCase)
{
for (int i=0; i{
bool ret = ContainsDuplicateCharFunc(TestCase[i].first);
if ( ret != TestCase[i].second )
{
cout << "Test case Failed:" << TestCase[i].first << " [expected]
"true":"false") << endl;
} else{
cout << "Test case Passed:" << TestCase[i].first << " [expected]
"true":"false") << endl;
}
}
}
// Unit Test
int main()
{
vector< pair > TestCase;
TestCase.push_back(make_pair("abc", false));
TestCase.push_back(make_pair("", false));
TestCase.push_back(make_pair("abcad", true));
TestCase.push_back(make_pair("aab", true));
TestCase.push_back(make_pair("abb", true));
TestCase.push_back(make_pair("abcda", true));
// Method 1:
cout << "Method 1:" << endl;
for (int i=0; i{
bool ret = ContainsDuplicateChar(TestCase[i].first);
if ( ret != TestCase[i].second )
{
cout << "Test case Failed:" << TestCase[i].first << " [expected]
"true":"false") << endl;
} else{
cout << "Test case Passed:" << TestCase[i].first << " [expected]
"true":"false") << endl;
}
}
cout << "Method 2:" << endl;
// Method 2:
for (int i=0; i{
bool ret = ContainsDuplicateCharNoExtraBuffer(TestCase[i].first);
if ( ret != TestCase[i].second)
{
cout << "Test case Failed:" << TestCase[i].first << " [expected]
"true":"false") << endl;
} else{
cout << "Test case Passed:" << TestCase[i].first << " [expected]
"true":"false") << endl;
}
}
// There are some duplicate for Method1 and Method2. We use function
object to handle this.
cout << "Call it with function pointer:" << endl;
doTest(ContainsDuplicateChar, TestCase);
doTest(ContainsDuplicateCharNoExtraBuffer, TestCase);
return 0;
}
