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

Given a string list words, as the dictionary of the language, the strings in words have been sorted alphabetically in the new language.

Please restore the known alphabetical order in this language according to the dictionary and arrange it in alphabetical order. If there is no legal alphabetical order, return "". If there are multiple possible legal alphabetic sequences, return any one of them.

There are two cases when the dictionary order of string s is less than that of string t:

• At the first different letter, if the letter in s precedes the letter in t in the alphabetical order of this alien language, the dictionary order of S is less than t.
• If the preceding min(s.length, t.length) letters are the same, when s.length < t.length, the dictionary order of S 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:""
Explanation: there is no legal alphabetical order, so it is returned "" . 

Tips:
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] It consists of lowercase English letters only

This question may not understand the meaning just after reading. Let's go through it with example 1 words = ["wrt","wrf","er","ett","rftt"].

• First, wrt and wrf, the first two characters wr are the same, while the third character "t" is different from f, and wrt precedes wrf, so the order of T precedes f.
• Next, wrf is different from er, the first character w is different from e, and wrf precedes er, so the order of w precedes E.
• Then, er and ett, the first character e is the same, while the second character r is different from t, so the order of r is before t.
• Finally, "et" is different from rftt. The first character e is different from r, so the order of e precedes r.
  We can synthesize the previous conclusions, T - > F, W - > e, R - > t, e - > R, so we can finally come to the conclusion that there is and only one order, namely "wertf".

The code implementation is as follows:

class Solution {
    public String alienOrder(String[] words) {
        boolean[] exist=new boolean[26];
        int[] in=new int[26];
        Set<Integer>[] edge=new HashSet[26];
        int count=0;
        for (int i=0;i<26;i++){
            edge[i]=new HashSet<Integer>();
        }
        for (int j=0;j<words.length;j++){
            String str=words[j];
            for (int k=0;k<str.length();k++){
                if (!exist[str.charAt(k)-'a']){
                    count++;
                    exist[str.charAt(k)-'a']=true;
                }
            }
        }

        for (int m=1;m< words.length;m++){
            String pre=words[m-1];
            String nex=words[m];
            int index=0;
            while (index<pre.length()&&index<nex.length()){
                if (pre.charAt(index)==nex.charAt(index))index++;
                else break;
            }
            if (index<pre.length()&&index<nex.length()){
                if (!edge[pre.charAt(index)-'a'].contains(nex.charAt(index)-'a')){
                    in[nex.charAt(index)-'a']++;
                    edge[pre.charAt(index)-'a'].add(nex.charAt(index)-'a');
                }
            }
            if (index<pre.length()&&index>=nex.length())return "";//Special judgment
        }
        
        Queue<Integer> queue=new LinkedList<>();
        StringBuilder sb=new StringBuilder();
        for (int i=0;i<26;i++){
            if (in[i]==0&&exist[i])queue.offer(i);
        }
        
        while (!queue.isEmpty()){
            int po=queue.poll();
            sb.append((char)(po+'a'));
            for (Integer ind:edge[po]){
                in[ind]--;
                if (in[ind]==0){
                    queue.add(ind);
                }
            }
        }
        return sb.length()==count?sb.toString():"";
    }
}

It should be noted that the test case has a special example: ["abc","ab"], which does not comply with the

If the preceding min(s.length, t.length) letters are the same, when s.length < t.length, the dictionary order of S is also less than t

Therefore, special judgment conditions are required.