Application-Algorithm/StoreAndSearchString.cpp at main · kimduong322/Application-Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*
Description
---------------------------------------------------------------------------------------------------------------------
A database contains a sequence of key k1, k2, ..., kn which are strings (1<=n<=100000).
Perform a sequence of actions of two kinds:
· find k: find and return 1 if k exists in the database, and return 0, otherwise
· insert k: insert a key k into the database and return 1 if the insertion is successful (k does not exist in the database)
and return 0 if the insertion is failed (k exists in the database)
Note that the length of any key is greater than 0 and less than or equal to 50.
---------------------------------------------------------------------------------------------------------------------
Input
Two blocks of information. The first block contains a key of (k1,k2,...,kn) in each line.
The first block is terminated with a line containing *.
The second block is a sequence of actions of two finds described above:
each line contains 2 string: cmd and k in which cmd = find or insert and k is the key (parameter of the action).
The second block is terminated with a line containing ***. Note that the number of actions can be up to 100000.
Output
Each line contains the result (0 or 1) of the corresponding action.
---------------------------------------------------------------------------------------------------------------------
*/

/*
---------------------------------------------------------------------------------------------------------------------
Example
Input

computer
university
school
technology
phone
*
find school
find book
insert book
find algorithm
find book
insert book
***

Output
1
0
1
0
1
0
---------------------------------------------------------------------------------------------------------------------
*/

#include <bits/stdc++.h>
using namespace std;

/*
    This version of code use dymanic array-vector in C++
    Using vector.push_back() to insert
    Using std::find(vector.begin(), vector.end(), target) to search
    Pros: familiar
    Cons: is not the best performance approach
*/
void StoreAndSearchStringVectorVersion() {
    vector<string> database;
    string key;
    do
    {
        cin >> key;
        if(key == "*") continue;
        database.push_back(key);
    } while (key != "*");

    string cmd, k;
    do
    {
        cin >> cmd;
        if (cmd == "***")
        {
            continue;
        }
        if (cmd == "find")
        {
            cin >> k;
            vector<string>::iterator result = find(database.begin(), database.end(), k); // O(n)
            if(result != database.end()) {
                cout << 1 << endl;
            } else cout << 0 << endl;
        }
        else if (cmd == "insert")
        {
            cin >> k;
            vector<string>::iterator result = find(database.begin(), database.end(), k); // O(n)
            if (result != database.end())
            {
                cout << 0 <<endl; // insert failed
            } else {
                database.push_back(k); // O(1)
                cout << 1 << endl; // insert successfull
            }
        }
    } while (cmd != "***");
}


void StoreAndSreachStringUnorderedSetVersion() {
    unordered_set<string> database;
    string key;
    do
    {
        cin >> key;
        if(key == "*") continue;
        database.insert(key);
    } while (key != "*");

    string cmd, k;
    do
    {
        cin >> cmd;
        if (cmd == "***")
        {
            continue;
        }
        if (cmd == "find")
        {
            cin >> k;
            if(database.find(k) != database.end()) {  // O(logn)
                cout << 1 << endl;
            } else cout << 0 << endl;
        }
        else if (cmd == "insert")
        {
            cin >> k;
            auto result = database.insert(k); // O(logn)
            if(result.second) {
                cout << 1 << endl;
            } else cout << 0 << endl;
        }
    } while (cmd != "***");
}

int main() {
    /* both "find" and "search" has complex O(logn)
    => faster than StoreAndSearchStringVectorVersion */
    StoreAndSreachStringUnorderedSetVersion();
    return 0;
}