(words []string)
| 6 | ) |
| 7 | |
| 8 | func alienOrder(words []string) string { |
| 9 | adjList := make(map[string]map[string]bool) |
| 10 | |
| 11 | // count the in-degree of each vertex |
| 12 | inDegrees := make(map[string]int) |
| 13 | for _, w := range words { |
| 14 | for _, r := range w { |
| 15 | inDegrees[string(r)] = 0 |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | // for word pair in the sorted list of words, find ordering |
| 20 | for i := 0; i < len(words)-1; i++ { |
| 21 | wordCurr := words[i] |
| 22 | wordNext := words[i+1] |
| 23 | minLen := int(math.Min(float64(len(wordCurr)), float64(len(wordNext)))) |
| 24 | |
| 25 | // for each character in both words, find ordering |
| 26 | for r := 0; r < minLen; r++ { |
| 27 | charCurr := string(wordCurr[r]) |
| 28 | charNext := string(wordNext[r]) |
| 29 | |
| 30 | // if the characters are not equal, then charCurr comes before charNext |
| 31 | if charCurr != charNext { |
| 32 | _, ok := adjList[charCurr] |
| 33 | if !ok { |
| 34 | adjList[charCurr] = make(map[string]bool) |
| 35 | } |
| 36 | |
| 37 | // if the ordering does not already exist, add it |
| 38 | // and increase the in-degree of the charNext |
| 39 | _, ok = adjList[charCurr][charNext] |
| 40 | if !ok { |
| 41 | adjList[charCurr][charNext] = true |
| 42 | inDegrees[charNext]++ |
| 43 | } |
| 44 | break |
| 45 | } |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | // get all vertices with a zero in-degree |
| 50 | zeros := make([]string, 0) |
| 51 | for vertex, degree := range inDegrees { |
| 52 | if degree == 0 { |
| 53 | zeros = append(zeros, vertex) |
| 54 | } |
| 55 | } |
| 56 | |
| 57 | // stable ordering for tests |
| 58 | sort.Strings(zeros) |
| 59 | |
| 60 | // if there are no zero in-degree vertices, there is a cycle |
| 61 | if len(zeros) == 0 { |
| 62 | return "" |
| 63 | } |
| 64 | |
| 65 | // return a topological sorting of the lexicographical ordering graph |
no outgoing calls