4ms C++ Topological Sort using DFS (NOT BFS) -Clean and clear code


  • 0
    F
    class Solution {
    protected:
        struct Node
        {
            char c = 'a', visited = 0;
            vector<char> children;
            Node (char cc = 'a', char v = 0):c(cc), visited(v){}
        };
        constexpr static size_t ASIZE = 26;
        array<Node *, ASIZE> nodes;
        string result;
        //return false if order is invalid
        bool compare(const string &stra, const string & strb)
        {
            int i = 0;
            for ( ;i < min(stra.size(), strb.size()) && stra[i] == strb[i] ; ++i);
            if (i == stra.size())
                return true;
            if (i == strb.size()) //b is longer than a and all b's chars appear in a
                return false;
            if (nodes[stra[i] - 'a'] == nullptr)
                nodes[stra[i] - 'a'] = new Node{stra[i]};
            nodes[stra[i] - 'a']->children.push_back(strb[i]);
            if (nodes[strb[i] - 'a'] == nullptr)
                nodes[strb[i] - 'a'] = new Node{strb[i]};
            return true;
        }
        //return false if order is invalid
        bool dfs(Node * node)
        {
            if (node == nullptr)
                return true;
            if (node->visited == 1)
                return false;
            if (node->visited == 2)
                return true;
            node->visited = 1;
            for (auto c : node->children)
                if (!dfs(nodes[c - 'a']))
                    return false;
            node->visited = 2;
            result.push_back(node->c);//store by reverse topological order
            return true;
        }
        //return false if order is invalid
        bool topologicalSort()
        {
            for (auto p : nodes)
                 if (!dfs(p))
                    return false;
            return true;
        }
    public:
        Solution ()
        {
            fill(begin(nodes), end(nodes), nullptr);
        }
        ~Solution()
        {
            for (auto p : nodes)
                 delete p ;
        }
        string alienOrder(vector<string>& words) {
            if (words.empty())
                return "";
            for (int i = 1; i < words.size(); ++i)
                if(!compare(words[i-1], words[i]))
                    return "";
            if (!topologicalSort())
                return "";
            reverse(result.begin(), result.end());
            //handle characters whose order can't be calculated.
            for (int i = 0; i < words.size(); ++i)
                for(int j = 0 ; j < words[i].size(); ++j)
                    if (nodes[words[i][j] - 'a'] == nullptr)
                    {
                        nodes[words[i][j] - 'a'] = new Node; //mark it
                        result.push_back(words[i][j]);
                    }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.