CareerCup1.1

CareerCup1.1.cpp

/* Chapter 1
 * 1.1 Implement an algorithm to determine if a string has all unique characters.
 * What if  you cannot use additional data structures?
 */

#include <iostream>
#include <string>
#include <cstring> // for memset()

using namespace std;

// brute-force: O(n^2) in time complexity, O(1) in space complexity
bool isUnique_brute(string str)
{
    for (int i = 0; i < str.length(); i++)
    {
        for (int j = 0; j < str.length(); j++)
        {
            if (str[i] == str[j] && i != j)
            {
                return false;
            }
        }
    }
    return true;
}

// Since Extended ASCII has at most 256 characters
// We can use array to record the appearance of each character
// Time-complexity is O(N), but it always need an array with size 256
bool isUnique_array(string str)
{
    bool ASCII[256];
    // set array to a specific value
    // memset(): http://www.cplusplus.com/reference/cstring/memset/
    memset(ASCII, 0, sizeof(ASCII));
    
    for (int i = 0; i < str.length(); i++)
    {
        // One thing need to address:
        // we cast char into int, however char range from 0~127
        // if string contains extended ASCII(128~255), value will be
        // range from -1 ~ -128, will lead to index error
        // Usually, test string will be printable ASCII(0~127)
        // It's Ok to use  int value = (int)str[i];
        // We can change it into  int value = (inst)str[i] + 128 to make it more rigid
        int value = (int)str[i] + 128;
        if (ASCII[value]) return false; // if corresponding slot has true, indicating already appeared before
        ASCII[value] = true; // denote the appearance
    }
    return true;
}


// Improve space complexity, same running time O(N)
// We can map value from 0~255 into 8 bits, since 2^8=256
// the bool array can shrink into size of 8
bool isUnique_8bits(string str)
{
    int bit[8];
    memset(bit, 0, sizeof(bit));
    
    for (int i = 0; i < str.length(); i++)
    {
        int value = (int)str[i] + 128;
        // tricky part
        // why use shift instead of just store the module in to index?
        // because bit[index] = module, and then use bit[index] == module
        // as condition can only detect "aab", but not "aba", since it just remembers
        // the last value. However, if you use shift, it will log all the history.
        // condition can use '&' to find if a specific value has ever appeared
        // e.g "aba":
        // index = 97/32 = 3, module = 97%32 = 1
        // bit[3] will be (0000 0010)
        // index = 98/32 = 3, module = 98%32 = 2
        // bit[3] will be (0000 0110)
        // index = 97/32 = 3, module = 97%32 = 1
        // now, check the condition:
        // bit[3] & (1 << module) will be 0000 0110 bit and 0000 0010
        // it will return true since the second bit is the same 1
        // therefore program return false -> not all unique
        int index = value/32, module = value%32;
        if (bit[index] & (1 << module)) return false;
        bit[index] |= (1 << module);
    }
    return true;
}

// if the string is made of a~z (97~122) or A~z(65~90), only need 1 bit array( or int check = 0)
// since index will be the same value%32 varies from 1 to 25
// But, you cannot detect "aA" using isUnique_1bit() if you treat 'a' and 'A' as different char
bool isUnique_1bit(string str)
{
    int check = 0;
    for (int i = 0; i < str.length(); i++)
    {
        int value = (int)str[i];
        int module = value%32;
        if (check & (1 << module)) return false;
        check |= (1 << module);
    }
    return true;
}
// main function for testing
int main()
{
    string str = "a?-*BACd3677d";  // test all except isUnique_1bit()
    string str2 = "crushandy"; // test all, especially for isUnique_1bit()
    
    // if (isUnique_brute(str) == false)
    // if (isUnique_array(str) == false)
    if (isUnique_8bits(str) == false)
    // if (isUnique_1bits(str2) == false)
    {
        cout << "Not all characters are unique." << endl;
    }
    else cout << "All characters are unique." << endl;
    
    return 0;
}