Alien Dictionary

1、BFS+trie树

2、用trie树建立graph图表；

3、用GRAPH图表建立ind；

4、用ind进行bfs，输出结果；

https://leetcode.com/problems/alien-dictionary/

class node {
public:
    char c;
    map<char, node*> child;

    node()
    {

    }

    node(char c)
    {
        this->c = c;
    }
};

class Solution {
public:
    string alienOrder(vector<string>& words) {
        int n = words.size();
        if(n == 0)
        {
            return "";
        }

        node* root = new node();
        map<char, vector<char>> graph;
        map<char, int> ind;

        for(int i = 0; i<words.size(); i++)
        {
            string word = words[i];

            if(i != 0 && (word != words[i-1]) && words[i-1].find(word ,0) == 0)
            {
                return "";
            }

            node* p = root;
            for(char c : word)
            {
                ind[c] = 0;

                for(auto& kv : p->child)
                {
                    if(graph.find(kv.first) == graph.end())
                    {
                        vector<char> vec;
                        graph[kv.first] = vec;
                    }
                    if(kv.first != c)
                    {
                        graph[kv.first].push_back(c);
                    }
                }

                if(p->child.find(c) == p->child.end())
                {
                    node* newnode = new node(c);
                    p->child[c] = newnode;
                }
                p = p->child[c];
            }
        }

        bool zeroDepend = true;

        for(auto& kv : graph)
        {
            //cout<<kv.first<<endl;
            if(ind.find(kv.first) == ind.end())
            {
                ind[kv.first] = 0;
            }

            if(kv.second.empty() == false)
            {
                zeroDepend = false;
            }

            for(char c : kv.second)
            {
                ind[c]++;
            }
        }

        if(zeroDepend == true)
        {
            //return "";
        }

        for(auto& kv : ind)
        {
            //cout<<kv.first<<" "<<kv.second<<endl;
        }

        vector<char> stack;
        for(auto& kv : ind)
        {
            if(kv.second == 0)
            {
                stack.push_back(kv.first);
            }
        }

        string order;
        while(!stack.empty())
        {
            char c = stack.back();
            stack.pop_back();
            order.push_back(c);

            for(char ch : graph[c])
            {
                ind[ch]--;
                if(ind[ch] == 0)
                {
                    stack.push_back(ch);
                }
            }
        }

        if(order.length() == ind.size())
        {
            return order;
        }
        else
        {
            return "";
        }
    }
};