Cp_Temp/Alien_Dictionary.cpp at master · Naman027/Cp_Temp · 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
class Solution{
    public:
    void DFSRec(vector<int> adj[], int u, stack<int> &st, vector<bool> &visited)
{
    visited[u] = true;

    for(auto v: adj[u])
    {
        if(visited[v] == false)
        {
            DFSRec(adj, v, st, visited);
        }
    }

    st.push(u);
}

string topologicalSort(vector<int> adj[], int V)
{
    stack<int> st;
    vector<bool> visited(V, false);

    for(int v=0; v < V; v++)
    {
        if(adj[v].size())
        {
            for(auto u: adj[v])
            {
                if(visited[u] == false)
                {
                    DFSRec(adj, u, st, visited);
                }
            }
        }
    }

    string res;
    while(st.empty() == false)
    {
        res += st.top() + 'a';;

        st.pop();
    }

    return res;
}

string findOrder(string words[], int N, int K)
{
    vector<int> adj[K];

    for(int i = 0; i < N-1; i++)
    {
        string word1 = words[i];
        string word2 = words[i+1];

        for(int j = 0; j < min(word1.size(), word2.size()); j++)
        {
            if(word1[j] != word2[j])
            {
                int index1 = word1[j] - 'a';
                int index2 = word2[j] - 'a';

                adj[index1].push_back(index2);

                break;
            }
        }
    }

    return topologicalSort(adj, K);
}
};