My 0ms c++ solution, beat 100%


  • 0

    I use a adjacent list to record order from each neighbour words pair, and use an array to record former letter numbers, then use toposort to produce the dictionary and return "" if there's cycle.

     class Solution {
        public:
            string alienOrder(vector<string>& words) {
                string ret = "";
                int adjlist[26][26];
                int arc[26],rec[26];
                memset(adjlist, 0, sizeof(adjlist));
                memset(arc, 0, sizeof(arc));
                memset(rec, 0, sizeof(rec));
                for(int i = 0; i < words[0].size(); i++) rec[words[0][i]-'a']++;
                for(int i = 1; i < words.size(); i ++){
                    for(int j = 0; j < words[i].size(); j++) rec[words[i][j]-'a']++;
                    int j = 0, len = min(words[i-1].size(), words[i].size()); 
                    while(j<len&&words[i-1][j]==words[i][j])
                    {
                        j++;
                    }
                    if(j < len&&!adjlist[words[i-1][j]-'a'][words[i][j]-'a']) {
                        adjlist[words[i-1][j]-'a'][words[i][j]-'a'] = 1;
                        arc[words[i][j]-'a']++;
                    }
                }
                for(int i = 0; i < 26; i++)
                {
                    if(!rec[i]) arc[i]= -1;
                }
                for(int i = 0; i < 26; i++)
                {
                    int j = 0;
                    while(j<26&&arc[j]!=0) j++;
                    if(j==26) break;
                    ret += (char)(j+'a');
                    arc[j] =-1;
                    for(int k = 0; k < 26; k++){
                        if(adjlist[j][k]==1) arc[k]--;
                    }
                }
                for(int i = 0; i < 26; i++)
                {
                    if(arc[i]>0) return "";
                }
                return ret;
            }
        };

Log in to reply
 

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