Sword finger offer II 114 Alien dictionary

Title Description

There is an alien language using English letters , The alphabetical order of this language is different from that of English .

Given a list of strings words , As a dictionary of this language ,words The string in has Sorted alphabetically in the new language .

Please restore the known alphabetical order in this language according to the dictionary , and In alphabetical order array . If there is no legal alphabetical order , return “” . If there are more than one possible legal alphabetical order , Return to it Any one Order is enough .

character string s Dictionary order is less than character string t There are two situations ：

• At the first different letter , If s The letters in this alien language are in the alphabetical order of t Before the middle letter , that s The dictionary order of is less than t .
• If the previous min(s.length, t.length) The letters are the same , that s.length < t.length when ,s The dictionary order is also less than t .

Example 1：

Input ：words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]
Output ：“wertf”
Example 2：

Input ：words = [“z”,“x”]
Output ：“zx”
Example 3：

Input ：words = [“z”,“x”,“z”]
Output ：“”
explain ： There is no legal alphabetical order , Therefore return “” .

Tips ：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] It's only made up of lowercase letters

analysis

First, let's talk about the loopholes in the topic , In the title “words The strings in have been sorted alphabetically in the new language ”, In fact, there are strings that are not arranged in order in the background use cases , For example 2, It may be thought of as z and x The size relationship of is not clear, so it is not in alphabetical order , But the last background use case of the topic is [“abc”,“ab”], The definition of dictionary order in the title is “ If the preceding characters are the same , that s.length < t.length when ,s The dictionary order is also less than t”, Obviously, the last use case does not conform to the lexicographic sorting rule , For this kind of bug, We can make a special judgment , That is, when the characters before two strings are the same , If long characters come first , Go straight back “”.

For the partial order of letters , We can compare adjacent strings one by one to determine , The problem to be solved is how to maintain the partial order relation , In particular, maintain transitive partial order relations , such as a < b, b < c, Our final answer needs to reflect a < c, The first reaction to seeing the topic is the union search set with extended domain , Then I think it's complicated , It is a simple topological sorting problem .

For two adjacent strings , such as abc and abd, With two Pointers p and q Point to the starting point of two strings respectively , Point to the same character , Then move to the right , Until you meet the first different character c and d, You can judge c < d 了 , Simultaneously from c Connect a directed edge to d That's it . We keep enumerating adjacent strings , Map their partial order relationship , Finally, the string sequence is transformed into a directed graph , As long as this digraph is DAG, There is a topological sequence , Just output , No topological sequence indicates that there are rings , Returns an empty string .

How to sort Topology ？ First, if there is a problem when creating a drawing a To b The edge of , Will b I'd like to add 1, After the mapping is completed, traverse all the entry degrees as 0 The characters of , Put it in the queue . When the queue is not empty , Take the team leader element , Add the header element to the final output sequence , At the same time, subtract the depth of the characters pointed to by the team header element 1, If the depth of a character becomes 0, Just join the queue . After the algorithm is completed, if there is still a penetration that is not 0 The point of , It shows that there is a ring , Returns an empty string .

There is a detail that needs attention , Background use cases also give examples like a,a Such use cases , For this use case , We don't know the partial order relation between it and other nodes , But you still need to output the characters that appear , So you can first words The characters that appear in it are recorded , In statistics, the score is 0 Node penetration of , Add this character in words This condition occurs in , The statistics of characters without partial order relation will not be omitted .

The official solution may be complicated , So the solution efficiency of topological sorting is still OK .

Code

class Solution {
public:
    int idx = 0,e[900],h[30],ne[900];
    int ind[30],q[30];
    bool st[30];
    void add(int a,int b){
        e[idx] = b,ne[idx] = h[a],h[a] = idx++;
    }
    string alienOrder(vector<string>& words) {
        int n = words.size();
        memset(h,-1,sizeof h);
        for(auto s : words){
            for(int j = 0;j < s.size();j++) st[s[j] - 'a'] = true;
        }
        for(int i = 0;i < n - 1;i++){
            string l = words[i],r = words[i + 1];
            int p = 0,q = 0;
            while(p < l.size() && q < r.size() && l[p] == r[p]) {
                p++,q++;
            }
            if(p != l.size()){
                if(q == r.size())   return "";// The use case has an illegal string sequence 
                add(l[p] - 'a',r[q] - 'a');
                ind[r[q]-'a']++;
            }
        }
        string ans = "";
        int hh = 0,tt = -1;
        for(int i = 0;i < 26;i++) {
            if(!ind[i] && st[i]) q[++tt] = i;
        }
        while(hh <= tt) {
            int u = q[hh++];
            ans += 'a' + u;
            for(int i = h[u];~i;i = ne[i]) {
                int j = e[i];
                ind[j]--;
                if(!ind[j])    q[++tt] = j;
            }
        }
        for(int i = 0;i < 26;i++) {
            if(ind[i])  return "";
        }
        return ans;
    }
};