Find String

/***

11.5

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.

EXAMPLE:

Input: find “ball” in {“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”,}

Output: 4

***/

#include

#include

using namespace std;

int findstr(string *str, string s, int begin, int end) {

    if(end < begin) return -1;

    int mid = (begin + end) / 2;

    if(str[mid] == s) return mid;

    if(str[mid] == “”) {

        int left = findstr(str, s, begin, mid-1);

        if(left != -1) return left;

        else return findstr(str, s, mid+1, end);

    } else if(str[mid] > s) {

        return findstr(str, s, begin, mid-1);

    } else return findstr(str, s, mid+1, end);

}

void main() {

    string str[] = {“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”};

    int sz = sizeof(str) / sizeof(string);

    int index = findstr(str, “ball”, 0, sz-1);

    cout<<index<<endl;

}

Find Index in a sorted array

/*** 11.3

Given a sorted array of n integers that has been rotated an unknown number of times,

write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

EXAMPLE

Input: find 5 in {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}

Output: 8(the index of 5 in array)

***/

#include

using namespace std;

int findIndex(int *a, int val, int begin, int end) {

    if(begin > end) {

        return -1;

    }       

    int mid = (begin + end) / 2;

    if(a[mid] == val) return mid;

    if(a[mid] > a[begin]) {

        if (a[begin] val)

            return findIndex(a, val, begin, mid-1);

        else findIndex(a, val, mid+1, end);

    } else if (a[mid] < a[begin])

    {

        if(a[begin] val)

            return findIndex(a, val, begin, mid-1);

        else findIndex(a, val, mid+1, end);

    } else {

        if (a[mid] != a[end])

            return findIndex(a, val, mid+1, end);

        else {

            int left = findIndex(a, val, begin, mid-1);

            int right = findIndex(a, val, mid+1, end);

            if (left != -1) return left;

            else return right;

        }

    }

}

void main() {

    int a[] = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};

    int sz = sizeof(a) / sizeof(int);

    int index = findIndex(a, 5, 0, sz-1);

    cout<<index<<endl;

}

Anagrams Sort String

/***

Write a method to sort an array of strings so that all the anagrams are next to each other.

***/

#include

#include

#include

#include

#include

using namespace std;

/* anagrams consist from same letters in different order.

   so just check the # of each letter and the length of string.  */

// idea: using hashtabel with chaining…

// how to implement hashtable????

class Anagrams

{

public:

    Anagrams(string *str, int sz);

    ~Anagrams();

    void sortbyAnagrams();

    void print_out_strings();

private:

    void add_new_map_entry(string, int);

    // — (position of string, sorted string)

    map<string, vector<int>> mymap;

    string *mystr;

    int size;

};

Anagrams::Anagrams(string *str, int sz)

{

    mymap.clear();

    mystr = str;

    size = sz;

}

Anagrams::~Anagrams()

{

    mymap.clear();

}

void Anagrams:: sortbyAnagrams() {

    map<string, vector<int>> :: iterator it;

   

    string *ptr, tempstr;

    int pos;

    // initial

    ptr = mystr;

    pos = 0;

    while(pos != size) {

       

        tempstr = *ptr;

        sort(tempstr.begin(), tempstr.end());

       

        it = mymap.find(tempstr);

       

        if(it != mymap.end()) it->second.push_back(pos);

        else add_new_map_entry(tempstr, pos);

        pos++;

        ptr++;

    }

}

void Anagrams::print_out_strings() {

    map<string, vector<int>> :: iterator it;

    string s;

    for(it = mymap.begin(); it != mymap.end(); it++) {

        int sz = it->second.size();

        for(int i = 0; i<sz; i++) {

            s = mystr[it->second.back()];

            it->second.pop_back();

            cout << s <<”  “;

        }

    }

}

void Anagrams::add_new_map_entry(string key, int pos) {

    vector<int> v;

    v.push_back(pos);

    mymap.insert(pair<string, vector<int>>(key,v));

}

void main() {

    string str[] = {“abc”, “ctt”, “acb”, “kaa”, “cba”, “ttc”};

    int s = sizeof(str) / sizeof(string);

    Anagrams ana(str, s);

    ana.sortbyAnagrams();

    ana.print_out_strings();

}

insertion Merge

/***

11.1

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

***/

/**

IDEA: copy B to concat A. start from the head of B using insertion sort.

**/

#include

using namespace std;

void exchange(int *a, int *b) {

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

}

int copyB2A(int *a, int szA, int *b, int szB) {

    int index = 0;

    int i = 0, j = 0;

    while(a[i] == 0) i++;

    if(i == szA) return 0;

    for(; i < szA; i++) {

        if(a[i] == 0) {

            if(index == 0) {

                index = i;

            }

            if(j < szB) {

                a[i] = b[j++];

            } else break;

        }

    }

    return index;

}

void merge(int *a, int index, int szB) {

    for(int i = index; i < szB + index; i++) {

        int j = i;

        while(a[j] < a[j-1]) {

            exchange(a+j, a+j-1);

            j–;

        }

    }

}

void main() {

    int a[] = {1, 3, 5, 7, 9, 0, 0, 0};

    int b[] = {2, 4, 6};

    int szA = sizeof(a) / sizeof(int);

    int szB = sizeof(b) / sizeof(int);

    int index;

    index = copyB2A(a, szA, b, szB);

    merge(a, index, szB);

    for(int i = 0; i < index + szB; i++)

        cout<<a[i]<<” “;

    cout << endl;

}