Straightforward C++ DFS code, using 26 indexes


  • 0
    N
    class Solution {
    public:
    	string alienOrder(vector<string>& words){
    		vector<vector<int>> graph(26, vector<int>());
    
    		vector<int> visited(26, 2); // 0: unvisited; 1: onPath; 2: visited
    
    		// build graph
    		for (auto str : words) {
    			for (int i=0; i<str.size()-1; i++) {
    				char thischar = str[i];
    				char nextchar = str[i+1];
    				visited[thischar-'a'] = 0;
    				visited[nextchar-'a'] = 0;
    				if (thischar!=nextchar) graph[thischar-'a'].push_back(nextchar-'a');
    			}
    		}
    		string res;
    		for (int i=0; i<26; i++) {
    			if (!visited[i] && !dfs_acyclic(graph, visited, res, i) ) return string();
    
    		}
    		reverse(res.begin(), res.end());
    		return res;
    	}
    
    	bool dfs_acyclic(vector<vector<int>>& graph, vector<int>& visited, string& res, int charidx) {
    		if (visited[charidx]==1) return false;
    		if (visited[charidx]==2) return true;
    		visited[charidx] = 1;
    		// further dfs
    		if (!graph[charidx].empty()) {
    			for (auto nextcharidx: graph[charidx]) {
    				if (!dfs_acyclic(graph, visited, res, nextcharidx)) return false;
    			}
    		}
    		// process this charidx
    		res.push_back(charidx+'a');
    		visited[charidx] = 2;
    		return true;
    	}
    };
    

Log in to reply
 

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