My solution using Topological sort


  • 0
    M
    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            int inDegree[26];
            memset(inDegree, -1, sizeof inDegree);
            vector<int> edge[30];
            int cnt = 0;
            for (int i = 0; i < words.size(); i++) {
                for (int j = 0; j < words[i].size(); j++) {
                    inDegree[words[i][j] - 'a'] = 0;
                }
            }
            for (int i = 0; i < 26; ++i) if (inDegree[i] >= 0) ++cnt; 
            for (int i = 1; i < words.size(); i++) {
                for (int j = 0; j < words[i].size() && j < words[i - 1].size(); j++) {
                    int c1 = words[i][j] - 'a', c2 = words[i - 1][j] - 'a';
                    if (c1 != c2) {
                        edge[c2].push_back(c1);
                        inDegree[c1]++;
                        break;
                    } else if (j + 1 == words[i].size() && words[i].size() < words[i - 1].size()) return "";
                }
            }
            queue<int> Q;
            for (int i = 0; i < 26; i++) {
                if (inDegree[i] == 0) Q.push(i);
            }
            string ret = "";
            
            while (!Q.empty()) {
                int t = Q.front(); Q.pop();
                ret += 'a' + t;
                --cnt;
                for (int i = 0; i < edge[t].size(); i++) {
                    inDegree[edge[t][i]]--;
                    if (inDegree[edge[t][i]] == 0) Q.push(edge[t][i]);
                }
            }
            if (cnt != 0) return "";
            return ret;
        }
    };
    

Log in to reply
 

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