4ms C++ solution using DFS


  • 0
    G
    class Solution {
    private:
        bool dfs(string& result, vector<char> successors[], int visited[], char c) {
            visited[c - 'a'] = 1;
            for (char v : successors[c - 'a']) {
                // visited[c - 'a'] == 0 represents c is never visited.
                // visited[c - 'a'] == 1 represents c has been just visited in the same search so there is a cycle in the graph which makes the order invalid.
                // visited[c - 'a'] == 2 represents c has been visited in a previous search.
                if ((visited[v - 'a'] == 0 && !dfs(result, successors, visited, v)) || visited[v - 'a'] == 1)
                    return false;
            }
            visited[c - 'a'] = 2;
            result = string(1, c) + result;
            return true;
        }
    public:
        string alienOrder(vector<string>& words) {
            int n = (int)words.size();
            vector<char> successors[26];
            bool exists[26] = {0};
            for (int i = 0; i != n; ++i) {
                for (char c : words[i]) exists[c - 'a'] = true;
                int len1 = (int)words[i].size(), len2 = i == n - 1 ? 0 : (int)words[i + 1].size(), j = 0;
                while (j != len1 && j != len2 && words[i][j] == words[i + 1][j]) ++j;
                if (j != len1 && j != len2) successors[words[i][j] - 'a'].push_back(words[i + 1][j]);
            }
            string result = "";
            int visited[26] = {0};
            for (char c = 'a'; c <= 'z'; ++c) {
                if (exists[c - 'a'] && !visited[c - 'a'] && !dfs(result, successors, visited, c)) 
                    return "";
            }
            return result;
        }
    };
    

Log in to reply
 

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