Share my C++ solution, Easy to understand and really fast!!!


  • 0
    J
    class Solution {
    public:
    string alienOrder(vector<string>& words) {
        int n=words.size();
        set<int> map[26];
        string res="";
        findRelation(words,map,0,n,0);
        int degree[26];
        for (int i=0;i<26;++i)
            degree[i]=-1;
        int count=0;
        for (int i=0;i<words.size();++i)
        {
            for (int j=0;j<words[i].length();++j)
            {
                if (degree[words[i][j]-'a']<0)
                {
                    degree[words[i][j]-'a']++;
                    count++;
                }
            }
        }
        for (int i=0;i<26;++i)
        {
            if (!map[i].empty())
            {
                for (auto p:map[i])
                degree[p]++;
            }
        }
        while (count>0)
        {
            vector<int> temp;
            bool found=false;
            for (int i=0;i<26;++i)
            {
                if (degree[i]==0)
                {
                    temp.push_back(i);
                    res.push_back('a'+i);
                    degree[i]--;
                    count--;
                    found=true;
                }
            }
            if (!found)
                return "";
            for (auto v:temp)
            {
                if (!map[v].empty())
                {
                    for (auto p:map[v])
                        degree[p]--;
                }
            }
        }
        return res;
    }
    void findRelation(vector<string>& words,set<int> map[],int start,int end,int k)
    {
        if (start+1>=end) return;
        int i=start;
        int j;
        string temp;
        while (i<end)
        {
            j=i;
            while (j<end && words[j][k]==words[i][k])
                j++;
            temp.push_back(words[i][k]);
            int t=i;
            while (t<end && words[t].length()==k+1)
                t++;
            findRelation(words,map,t,j,k+1);
            i=j;
        }
        for (i=0;i<temp.length()-1;++i)
        {
            map[temp[i]-'a'].insert(temp[i+1]-'a');
        }
    }
    };

Log in to reply
 

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