269. Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

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: The order is invalid, so return "".

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 100

• words[i] consists of only lowercase English letters.

Solution

Using topologically sort, to find a Directed Acyclic Graph exploring the order.

There are three steps to do topologically sort with BFS.

• Build the material that we need - A graph (Map or Array of Set) to record the out directed(->) nodes of the node - A in-degree values information for all nodes in the graph

• Add the nodes that its degree value is 0 to the queue, then start with the BFS

• Constantly decrease the degree for the adjacent nodes of the visited node's

• If the visited node's degree is down to 0, then add it into the queue

• During the poll out of the queue, add the node into the return string

class Solution {
    public String alienOrder(String[] words) {
        if(words.length == 0 || words == null) return "";
        
        HashMap<Character, Integer> degree = new HashMap<>();
        Set<Character>[] relationships = new HashSet[26];
        for(int i = 0; i < 26; i++){
            relationships[i] = new HashSet<Character>();
        }
        
        //relationships[0] // the characters shall  be after the 'a' in alein order    
        for(int i = 0; i < words.length; i++) {
            for(int j = 0; j < words[i].length(); j++) {
                degree.put(words[i].charAt(j), 0);
            } 
        }  
        
        for(int i = 0; i+1 < words.length; i++) {
            String cur = words[i];
            String next = words[i+1];
            
            if(!isLexicographically(cur, next)) return "";
            int min = Math.min(cur.length(), next.length());
            for(int j = 0; j < min; j++) {
                char c1 = cur.charAt(j);
                char c2 = next.charAt(j);
                if(c1 != c2) {
                    if(!relationships[c1-'a'].contains(c2)) {
                        relationships[c1-'a'].add(c2);
                        degree.put(c2, degree.get(c2) + 1);
                    }
                    break;
                }
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        for(Character c : degree.keySet()){
            if(degree.get(c) == 0) {
                queue.add(c);
            }
        }
        
        String ret = "";
        while(!queue.isEmpty()) {
            char c = queue.poll();
            ret += c;
            for(char next : relationships[c-'a']){
                degree.put(next, degree.get(next) - 1);
                if(degree.get(next) == 0) {
                    queue.add(next);
                }
            }
        }
        if(ret.length() != degree.size()) return "";
        return ret;
        
    }
    
    public boolean isLexicographically(String s1, String s2){
        return !(s1.length() > s2.length() && s1.startsWith(s2));
        
    }
}