Alien Dictionary

Hard

The problem

words is a list of words from an alien language, sorted in that language's alphabet order. Work out the order of the letters and return them as a string, using only the letters that appear in words. If the list contradicts itself (no valid letter order exists), return an empty string.

Example 1
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Comparing neighbouring words: t comes before f, w before e, r before t, e before r. That forces w, e, r, t, f.
Example 2
Input: words = ["z", "x", "z"]
Output: ""
The first two words say z is before x, and the last two say x is before z.
Example 3
Input: words = ["abc", "ab"]
Output: ""
A longer word cannot come before its own shorter prefix.

Limits

1 ≤ len(words) ≤ 100
1 ≤ len(words[i]) ≤ 100
Words use only lowercase English letters
When the order is not forced, any valid order may be accepted

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Compare adjacent words: the first different letter tells you one ordering rule between two letters.

The idea

Build edges from adjacent word pairs (watch for the invalid "abc" before "ab" case), then topologically sort; a cycle means no valid order.

Target: O(total characters) time

Go function shape

func foreignDictionary(words []string) string

Reference solution

Tested with go test. Try it yourself first, then compare.

// AlienOrder: letter order implied by a sorted list of words, or "" if it is contradictory.
func AlienOrder(words []string) string {
	next := map[byte]map[byte]bool{}
	indeg := map[byte]int{}
	for _, w := range words {
		for i := 0; i < len(w); i++ {
			if _, ok := indeg[w[i]]; !ok {
				indeg[w[i]] = 0
				next[w[i]] = map[byte]bool{}
			}
		}
	}
	for i := 0; i+1 < len(words); i++ {
		a, b := words[i], words[i+1]
		if len(a) > len(b) && a[:len(b)] == b {
			return "" // "abc" can never come before "ab"
		}
		for j := 0; j < len(a) && j < len(b); j++ {
			if a[j] != b[j] { // the first difference is the only rule this pair gives us
				if !next[a[j]][b[j]] {
					next[a[j]][b[j]] = true
					indeg[b[j]]++
				}
				break
			}
		}
	}
	var queue []byte
	for c := 'a'; c <= 'z'; c++ { // fixed scan order keeps the output deterministic
		if d, ok := indeg[byte(c)]; ok && d == 0 {
			queue = append(queue, byte(c))
		}
	}
	var out []byte
	for len(queue) > 0 {
		c := queue[0]
		queue = queue[1:]
		out = append(out, c)
		var outs []byte
		for to := range next[c] {
			outs = append(outs, to)
		}
		sort.Slice(outs, func(i, j int) bool { return outs[i] < outs[j] })
		for _, to := range outs {
			if indeg[to]--; indeg[to] == 0 {
				queue = append(queue, to)
			}
		}
	}
	if len(out) != len(indeg) {
		return "" // a cycle: some letters never reached in-degree 0
	}
	return string(out)
}

Read the lesson: Advanced Graphs · Dijkstra & Spanning Trees