Same Topological Sort(DFS) as in Course Schedule


  • 0
    L

    comments inline

    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            vector<unordered_set<int> > graph(26);
            vector<bool> visited(26, false), onpath(26, false);
            string s; // result
            bool success = buildGraph(words, graph);
            if (!success) return "";
            for (int i=0; i<26; ++i) {
                if (!graph[i].empty() && dfs_cycle(graph, i, visited, onpath, s)) return "";
            }
            reverse(s.begin(), s.end());
            return s;
        }
        
        bool buildGraph(vector<string>&words, vector<unordered_set<int> > &graph) {
            for (auto &str : words) {
                for (auto c : str) {
                    graph[c-'a'].insert(c-'a'); //insert itself. otherwise "wxyz", "wxyc" will only output "z, c"; the "w,x,y" will be ignored due to the way the graph is built below
                }
            }
            for (int i=0; i<words.size()-1; ++i) {
                int mn = min(words[i].size(), words[i+1].size()), j=0;
                for (; j<mn; ++j) {
                    if (words[i][j]!=words[i+1][j]) {
                        graph[words[i][j]-'a'].insert(words[i+1][j]-'a'); // find known sequence from input
                        break;
                    }
                }
                if (j==mn && words[i].size() > words[i+1].size()) return false;// this is to handle case "wxyz, wxy" where the order of z and w,x,x is unknown. So return "" eventually
            }
            return true;
        }
        
        bool dfs_cycle(vector<unordered_set<int> >&graph, int node, vector<bool> &visited, vector<bool> & onpath, string &s) {
            if (visited[node]) return false;
            visited[node]=onpath[node]=true;
            for (auto &neig : graph[node]) {
                if(node == neig) continue; // for char itself, ignore
                if (onpath[neig] || dfs_cycle(graph, neig, visited, onpath, s)) 
                    return true;
            }
            onpath[node]=false;
            s+=(char(node+'a'));
            return false;
        }
    };
    

Log in to reply
 

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