learningcpp/anagrams.cc at master · RamanVerma/learningcpp · 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
#include <cctype>
#include <iostream>
#include <string>
#include <memory>

using namespace std;
struct node {
public:
    node (char k, int count)
        : key(k),
        cnt(count),
        lchild(nullptr),
        rchild(nullptr)
    {}
    void
    insert (char k)
    {
        if (k == key) {
            cnt++;
            return;
        }
        if (k < key) {
            if (lchild) {
                lchild->insert(k);
            } else {
                lchild = unique_ptr<struct node> (new struct node (k, 1));
            }
        } else {
            if (rchild) {
                rchild->insert(k);
            } else {
                rchild = unique_ptr<struct node>(new struct node (k, 1));
            }
        }
    }
    bool
    find (char k, int count)
    {
        if ((k == key) && (cnt == count)) {
            return true;
        }
        if (k < key) {
            if (lchild) {
                lchild->find (k, count);
            } else {
                return false;
            }
        } else {
            if (rchild) {
                rchild->find (k, count);
            }else {
                return false;
            }
        }
    }
    bool
    findAll (const struct node &root)
    {
        if (! find (root.key, root.cnt)) {
            return false;
        }
        if (root.lchild && ! findAll (*(root.lchild))) {
            return false;
        }
        if (root.rchild && ! findAll (*(root.rchild))) {
            return false;
        }
        return true;
    }
    char key;
    int cnt;
    unique_ptr<struct node> lchild;
    unique_ptr<struct node> rchild;
};
typedef struct node node;

bool
anagrams (const string &w1, const string & w2)
{
    if (w1.length() != w2.length()) {
        return false;
    }
    node root = node(w1[0], 1);
    for (size_t i = 1; i < w1.length(); i++)
    {
        root.insert(w1[i]);
    }
    node root2 = node(w2[0], 1);
    for (size_t i = 1; i < w2.length(); i++)
    {
        root2.insert(w2[i]);
    }
    return root.findAll (root2);
}

int
main (int argc, char *argv[])
{
    string w1;
    string w2;
    cout << "Enter the first word/sentence" << endl;
    getline(cin, w1);
    string w11;
    for (auto c: w1)
    {
        if (!isspace(c)) {
            w11 += tolower(c);
        }
    }
    cout << "Enter the second word/sentence" << endl;
    getline(cin, w2);
    string w21;
    for (auto c: w2)
    {
        if (!isspace(c)) {
            w21 += tolower(c);
        }
    }
    string message = w1 + " " +  w2 + " are " + (anagrams(w11, w21) ? "anagrams" : "not anagrams");
    cout << message << endl;
}