ac solution code


  • 0

    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)]
        }
    }
    

    0_1485899332986_Evernote Camera Roll 20170131 134640.jpg


Log in to reply
 

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