leetcode/find_like_words.cpp at master · Mayank-Parasar/leetcode · 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
//
// Created by Mayank Parasar on 2020-04-06.
//

/*
 * INPUT:
"God likes good dog"

God - 'g' 'o' 'd'
good - 'g' 'o' 'd'
dog - 'g' 'o' 'd'

case, frequency, order - does not matter
SIMILAR words

OUTPUT:
{God, good, dog}
 * */

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

string mysort(string str) {

    bool swap_ = true;
    while(swap_) {
        swap_ = false;
        for (int ii = 0; ii < str.length() - 1; ii++) {
            if (str[ii] > str[ii + 1]) {
                swap(str[ii], str[ii+1]);
                swap_ = true;
            }
        }
    }
    return str;
}


string remove_duplicate(string str) {
    string result;

    for(int ii = 0; ii < str.length()-1; ii++) {
        if(str[ii] == str[ii+1]) {
            continue;
        }
        else{
            result +=str[ii];
        }
    }

    result += str[str.length() - 1];

    return result;
}

vector<string> mysort(vector<string> string_vec) {
    vector<string> result;
    for(auto i : string_vec) {
        result.push_back(mysort(i));
    }

    return result;
}

vector<string> vecotize_string(string str) {
    vector<string> result;
    string tmp;
    for(int ii = 0; ii < str.length(); ii++) {
        tmp += str[ii];
        if(str[ii+1] == ' ' || str[ii+1] == '\0') {
            result.push_back(tmp);
            tmp = "";
            ii++;
        }
    }
    return result;
}

int main() {

    string str_orig = "God likes good dog and dog";
//    string str_orig = "Name of the game is Name";

    string str(str_orig);
    // remove case-sensitivity
    transform(str.begin(), str.end(), str.begin(), ::tolower);

    // vectrozie the string
    vector<string> vec_string = vecotize_string(str);
    vector<string> vec_string_orig = vecotize_string(str_orig);

    // sort all the charactar within the words in a vector
    vector<string> vec_string_sorted = mysort(vec_string);

    // now remove the duplicates from each string
    vector<string> vec_string_sorted_unique;
    for(auto i : vec_string_sorted) {
        vec_string_sorted_unique.push_back(remove_duplicate(i));
    }

    // now have a map of string and vector<int>
    // this will record the indecies of similar words
    map<string, vector<int>> mymap;
    for(int ii=0; ii < vec_string_sorted_unique.size(); ii++) {
        mymap[vec_string_sorted_unique[ii]].push_back(ii);

    }

    cout << "similar words are: " << endl;

    // print out this map:
    for(auto i : mymap) {
        cout << "{ ";
        for(auto k : i.second) {
            cout << vec_string_orig[k] << " ";
        }
        cout << " }";
        cout << endl;
    }
    return 0;
}