3ms C++ solution, beats 100% of cpp submission


  • 0
    D

    My algorithm is typical: 1. construct the graph, and 2. topological sort.

    For constructing the graph, I use a vertical approach by comparing letters column-by-column. Many top answers constructed the graph by comparing letters of 2 consecutive rows. I checked both the algorithms but the run time was the same so the reason which makes my code faster than others may lay on the topological sort.

    For topological sort, I use BFS and detect the feasibility by comparing the length of the result with the number of available characters. The traversal is done by checking the nodes whose in-edges are 0 repeatedly. This should be faster than using hash directly.

    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            bool chars[26] = {false};
            bool order[26][26] = {false};
            findOrder(words, 0, words.size(), 0, order, chars);
            
            int in_edges[26] = {0};
            int num_chars = 0;
            for (int i = 0; i < 26; ++i) {
                if (chars[i]) {
                    for (int j = 0; j < 26; ++j) {
                        if (order[i][j])
                            in_edges[j]++;
                    }
                    ++num_chars;
                }
            }
            queue<int> q;
            for (int i = 0; i < 26; ++i) {
                if (chars[i] && in_edges[i] == 0)
                    q.emplace(i);
            }
            
            string result;
            while (!q.empty()) {
                int cur = q.front(); q.pop();
                result += cur + 'a';
                for (int i = 0; i < 26; ++i) {
                    if (order[cur][i]) {
                        if (--in_edges[i] == 0)
                            q.emplace(i);
                    }
                }
            }
            
            return result.length() == num_chars ? result : "";
        }
        
        void findOrder(const vector<string>& words, int begin, int end, int pos, bool order[][26], bool chars[]) {
            if (pos < words[begin].length())
                chars[words[begin][pos] - 'a'] = true;
            for (int i = begin + 1; i < end; ++i) {
                if (pos < words[i - 1].length() && pos < words[i].length() && words[i-1][pos] != words[i][pos]) {
                    order[words[i-1][pos] - 'a'][words[i][pos] - 'a'] = true;
                    chars[words[i-1][pos] - 'a'] = true;
                    chars[words[i][pos] - 'a'] = true;
                }
            }
            
            
            int i = begin; 
            while (i < end) {
                while (i < end && pos >= words[i].length()) ++i;
                if (i == end)
                    break;
                int prev = i;
                ++i;
                while (i < end && pos < words[i].length() && words[i-1][pos] == words[i][pos])   ++i;
                findOrder(words, prev, i, pos + 1, order, chars);
            }
        }
    };
    

Log in to reply
 

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