Leetcode: Alien Dictionary

This question is asked very commonly at Facebook, and there are aliens in this problem, which gives it a nice twist. You are given a list of strings from the dictionary, where words are sorted lexicographically by the rules of the new language. Derive the order of the letters in this language and return it. Return any of the solutions if there are multiple of them. 

First, let's look up what lexicographic order is.

It's the generalization of the alphabetical order of the dictionaries to sequences of ordered symbols in an ordered set. This video assumes you have confidence in graph algorithms, such as breadth-first search and depth-first search.

Here's a few things to keep in mind: 

1. The letters within a word don't tell us anything about the relative order of the word. 

2. The input can contain words followed by their prefix, and we need to make sure this solution detects these cases correctly.

3. There can be more than one alphabet ordering

4. the output must contain all unique letters that were in the order list, including those that can be in any position, with no letters that are in the input.

This was extremely confusing, but on to the next part I guess. 

The first approach to try is breadth-first earch, which has

1. Get as much information about the alphabet order as possible

2. Represent the information in a meaningful way

3. Assume valid alphabet ordering.

Part 1 was extracting information. Let's start with an "alien language" and see how much we can conclude with simple reasoning.

We see the first order of the words in alphabet. Here's an example or a corpus and the first words in order. We remove the 4 duplicates afterwards. 

wxqkj

whqg

cckgh

cdxdt

cdht

ktgxt

ktdw

jqw

jmc

jmg

as a result, the starting letters are

[w w c c c c k k k k j j]

remove the duplicates now. 

[w c k j]

and now we know the relative order of the four letters inside of the dictionary. However, we might not know the order of the rest of the letters, unfortunately. 

Looking at the first 2 words wxqkj and whgg, means that the letter x goes before the letter h, so this means [w, c, k, j] [x, h] is the list.

Looking at this, we can make some lexicographical arrangements from this.

From this we can learn that

x->h

w->c

c->d

c->g

x->h

c->k

x->c

g->d

w->c

k->j

q->m

c->g

and this completes the first part, we represent these relations in an array and we can attempt to build chains in them, with some letters in more than one chain. 

w->c -> k -> j

w->c->d

x->c->k->j

q->graph is the best of visualizing these relations.

Drawing a graph results in the following:

The next thing we do is to assume a valid ordering, a valid start is something that is not a children of any nodes, which is 

q w t x. 

We remove these from the graph and continue to do topological sort by seeing the other root nodes,

q w t x m h c

q w t x m h c g k 

q w t x m h c g k j d

Now we are ready to make the algorithms.

So first we have to extract the order and the relations and insert them into an adjacency list. We then need to identify which letters have no incoming links left. This is really hard to do. alternatively we can 2 adjacency lists, one indicating the number of incoming edges that each letter has. 

We perform BFS for all letters that are reachable adding each letter to the output as soon as it's reachable using a queue. 

class Solution {

    public String alienOrder(String[] words) {

        //adjacency list and the number of direct parent nodes

        Map<Character, List<Character>> adjList = new HashMap<>(); 

        Map<Character, Integer> counts = new HashMap<>();

        

        //put every character in the counts and the adjacency list.  

        for(String word : words) {

            for(char c: word.toCharArray()) {

                counts.put(c, 0); 

                adjList.put(c, new ArrayList<>());

            }

        }

        for(int i = 0; i < words.length - 1; i++) {

            //compare 2 different words

            String word1 = words[i];

            String word2 = words[i + 1];

            //Return nothing if the lexigraphical order is messed up.

            if(word1.length() > word2.length() && word1.startsWith(word2) return "";

            for(int j = 0; j < Math.min(word1.length(), word2.length()); j++) {

                //find the first character, add the adjacency list from first -> second

                //then add a predecessor (first word) to the second word.

                if(word1.charAt(j) != word2.charAt(j)) {

                    adjList.get(word1.charAt(j)).add(word2.charAt(j));

                    counts.put(word2.charAt(j), counts.get(word2.charAt(j)) + 1;

                    break;

                }

            }

        }

    //Breadth-First Search.

    StringBuilder sb = new StringBuilder();

    Queue<Character> queue = new LinkedList<>();

    for(Character c: counts.keySet()) {

        if(counts.get(c).equals(0)) {

            queue.add(c);

        }

    }

    //append the character in a first in first out manner lexicographically.

    while(!queue.isEmpty()) {

        Character c = queue.remove();

        sb.append(c);

        for(Character next : adjList.get(c)) {

            counts.put(next, counts.get(next) - 1);

            if(counts.get(next).equals(0)) {

                queue.add(next);

            }

        }

    }

    if(sb.length() < counts.size()) {

        return  "";

    }

    //return the corresponding string.

    return sb.toString();

    }

}