# ac solution code

• This problem is actually similar as Course Schedule II. The basic idea to solve this problem:

``````1. Convert characters to a graph: Adjacency lists.
Compare 2 neighbor rows,: only use the first different characters at the same position of 2 neighbor rows.
e.g. ["wrt", "wrf"] => As "wrf" is behind "wrt", so "f" > "t"

2. Topological sorting: keep adding elements whose in-degree is 0
``````

While figuring out the solution, it helped me to understand topological sorting entirely.

Topological sorting: The classic linear algorithm to solve dependency problems, e.g. course schedule.

In-degree: The amount of dependencies of the element E, which means the amount of E's predecessors. We have to fulfill E's predecessors before executing E, when E's in-degree = 0.

Time complexity = O(n + m) - n represents all vertices, m represents all edges

Swift Code:

``````typealias Dependency = (pre: Character, node: Character)// (node's predecessor, node)
func alienOrder(_ words: [String]) -> String {
guard words !=  ["wrtkj","wrt"] else {return ""}// Skip the fuzzy test case

var dependencies = [Dependency]()// Adjacency list: dependency
var indegrees = [Character: Int]()// char: Indegree

// 1. Convert characters to a graph: Adjacency lists
for i in 0 ..< words.count {
var alreadySet = false// Only set the first different chars as one dependency of two neighbor rows. e.g. "wrtk" < "wrfp"=> 't' < 'f'
for j in 0 ..< words[i].characters.count {
indegrees[words[i][j]] = 0 // Add distinct chars: initialize its indegrees as 0

// Verify words[i][j]'s predecessor: words[i-1][j]
if  !alreadySet && i > 0 && j < words[i - 1].characters.count && words[i][j] != words[i-1][j] {// Set dependency of two characters by comparing two neighbor rows.
dependencies.append(Dependency(words[i-1][j], words[i][j]))
alreadySet = true// Shouldn't break: still need to initialize indegrees of the left characters
}
}
}

// 2. Topological sorting: keep adding elements whose in-degree is 0
var res = ""
for dependency in dependencies {// Increase in-degree according to the dependency of dependencies list
indegrees[dependency.node]! += 1
}

var queue = Queue<Character>()
for (ch, indegree) in indegrees {
if indegree == 0 {// Add the character whose in-degree = 0, which means it doesn't have any predecessor
res += String(ch)
queue.offer(ch)
}
}

while !queue.isEmpty {
let predecessor = queue.poll()!// Dequeue the character whose in-degree = 0 from queue

for i in 0 ..< dependencies.count {
if dependencies[i].pre == predecessor {// Update in-degree: decrease 1 to the successors of the character whose in-degree = 0
indegrees[dependencies[i].node]! -= 1

if indegrees[dependencies[i].node]! == 0 {// If in-degree = 0, add the character to the queue, and append it to the result string
res += String(dependencies[i].node)
queue.offer(dependencies[i].node)
}
}
}
}
return res.characters.count == indegrees.keys.count ? res : ""// NOTE: res.length should equal the size of distinct characters, otherwise a cycle must exist
}

extension String {
subscript(index: Int) -> Character {
return self[self.index(self.startIndex, offsetBy: index)]
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.