Simple idea based on DFS [4ms] in C++


  • 2
    W

    My idea is very straight-forward.
    First use the dictionary vector to construct a graph using adjacency matrix and the diagonal elements is used to store whether the alphabet appears in the dictionary or not.
    Then perform DFS to find the sequence for each potential root node.
    If there is a cycle or unvisited node, return "".

    class Solution {
    public:
        void findEdges(string &word1, string &word2, bool graph[][26]){
            // construct the graph
            int tmpLen = min(word1.length(), word2.length());
            for (int i = 0; i < tmpLen; i++){
                if (word1[i] != word2[i]){
                    graph[word1[i]-'a'][word2[i]-'a'] = true;
                    break;
                }
            }
        }
        bool dfs(string &res, vector<bool> &tmpMark, bool graph[][26], int root){
            // perform topological sort, return whether there is a cycle
            if (tmpMark[root]){
                res = "";
                return true;
            }
            tmpMark[root] = true;
            for (int i = 0;i < 26; i++){
                if (i != root && graph[root][i]){
                    if (dfs(res, tmpMark, graph, i)){
                        return true;
                    }
                }
            }
            graph[root][root] = false;
            tmpMark[root] = false;
            char tmp = root + 'a';
            res = tmp + res;
            return false;
        }   
        
        string alienOrder(vector<string>& words) {
            string res;
            if (words.size() == 0){
                return res;
            }
            if (words.size() == 1) return words[0];
            bool graph[26][26] = {false};
            for (char c : words[0]){
                graph[c-'a'][c -'a'] = true;
            }
            for (int i = 1; i < words.size(); i++){
                for (char c : words[i]){
                    graph[c -'a'] [c -'a'] = true;
                }
                findEdges(words[i-1], words[i], graph);
            }
            
            for (int i = 0; i < 26; i++){
                // find a root node;
                bool rootNode = graph[i][i];
                if (graph[i][i]){
                    for (int j = 0; j < 26; j++){
                        if ( j != i && graph[j][i]){
                            rootNode = false;
                            break;
                        }
                    }
                }
                if (rootNode){
                    string tmpRes = "";
                    vector<bool> tmpMark(26, false);
                    if (dfs(tmpRes, tmpMark, graph, i))
                        return "";
                    else
                        res += tmpRes;
                }
            }
            
            // if there is still unvisited node, return "";
            for (int i = 0; i < 26; i++){
                if (graph[i][i]) return "";
            }
            return res;
        }
    };

Log in to reply
 

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