Swift solution - iterative, DFS


  • 0
    class Solution {
        func findItinerary(_ tickets: [[String]]) -> [String] {
            var flights = [String: Heap<String>]()
            var path = [String]()
            var stack = ["JFK"]
            
            for ticket in tickets {
                if !flights.keys.contains(ticket[0]) {
                    flights[ticket[0]] = Heap(sort: { (_ a: String, _ b: String) -> Bool in
                        return self.compare(a, b)
                    })
                }
                flights[ticket[0]]?.insert(ticket[1])
            }
            while !stack.isEmpty {
                while flights.keys.contains(stack.last!) && !(flights[stack.last!]?.isEmpty)! {
                    stack.append(flights[stack.last!]!.remove()!)
                }
                path.insert(stack.removeLast(), at: 0)
            }
            
            return path
        }
        
        func findItinerary_DFS(_ tickets: [[String]]) -> [String] {
            var flights = [String: Heap<String>]()
            var path = [String]()
            
            for ticket in tickets {
                if !flights.keys.contains(ticket[0]) {
                    flights[ticket[0]] = Heap(sort: { (_ a: String, _ b: String) -> Bool in
                        return self.compare(a, b)
                    })
                }
                flights[ticket[0]]?.insert(ticket[1])
            }
            DFS("JFK", &flights, &path)
            
            return path
        }
        
        private func DFS(_ departure: String, _ flights: inout [String: Heap<String>], _ path: inout [String]) {
            while flights.keys.contains(departure) && !flights[departure]!.isEmpty {
                DFS(flights[departure]!.remove()!, &flights, &path)
            }
            path.insert(departure, at: 0)
        }
        
        private func compare(_ a: String, _ b: String) -> Bool {
            let aCharacters = Array(a.characters)
            let bCharacters = Array(b.characters)
            var i = 0
            
            while i < aCharacters.count && aCharacters[i] == bCharacters[i] {
                i += 1
            }
            
            if i == aCharacters.count {
                return false
            }
            
            return String(aCharacters[i]).asciiValueOfCharacter < String(bCharacters[i]).asciiValueOfCharacter
        }
    }
    
    public struct Heap<T> {
        var elements = [T]()
        // (>)max-heap or (<)min-heap
        fileprivate var isOrderedBefore: (T, T) -> Bool
        
        public init(sort: @escaping (T, T) -> Bool) {
            self.isOrderedBefore = sort
        }
        
        public init(array: [T], sort: @escaping (T, T) -> Bool) {
            self.isOrderedBefore = sort
            buildHeap(fromArray: array)
        }
        
        fileprivate mutating func buildHeap(fromArray array: [T]) {
            self.elements = array
            for i in stride(from: (self.elements.count / 2 - 1), through: 0, by: -1) {
                shiftDown(i, heapSize: self.elements.count)
            }
        }
        
        mutating func shiftDown(_ index: Int, heapSize: Int) {
            var parentIndex = index
            
            while true {
                let leftChildIndex = self.leftChildIndex(ofIndex: parentIndex)
                let rightChildIndex = leftChildIndex + 1
                var first = parentIndex
                
                if leftChildIndex < heapSize && isOrderedBefore(self.elements[leftChildIndex], elements[first]) {
                    first = leftChildIndex
                }
                if rightChildIndex < heapSize && isOrderedBefore(self.elements[rightChildIndex], elements[first]) {
                    first = rightChildIndex
                }
                if first == parentIndex {
                    return
                }
                
                swap(&self.elements[parentIndex], &self.elements[first])
                parentIndex = first
            }
        }
        
        mutating func shiftDown() {
            shiftDown(0, heapSize: self.elements.count)
        }
        
        mutating func shiftUp(_ index: Int) {
            var childIndex = index
            let child = self.elements[childIndex]
            var parentIndex = self.parentIndex(ofIndex: childIndex)
            
            while childIndex > 0 && isOrderedBefore(child, self.elements[parentIndex]) {
                self.elements[childIndex] = self.elements[parentIndex]
                childIndex = parentIndex
                parentIndex = self.parentIndex(ofIndex: childIndex)
            }
            
            self.elements[childIndex] = child
        }
        
        @inline(__always) func parentIndex(ofIndex i: Int) -> Int {
            return (i - 1) / 2
        }
        
        @inline(__always) func leftChildIndex(ofIndex i: Int) -> Int {
            return 2 * i + 1
        }
    
        @inline(__always) func rightChildIndex(ofIndex i: Int) -> Int {
            return 2 * i + 2
        }
        
        public var isEmpty: Bool {
            return self.elements.isEmpty
        }
        
        public var count: Int {
            return self.elements.count
        }
        
        public func peek() -> T? {
            return self.elements.first
        }
        
        public mutating func insert(_ value: T) {
            self.elements.append(value)
            shiftUp(self.elements.count - 1)
        }
        
        @discardableResult public mutating func remove() -> T? {
            if self.elements.isEmpty {
                return nil
            } else if self.elements.count == 1 {
                return self.elements.removeLast()
            } else {
                let value = self.elements[0]
                self.elements[0] = self.elements.removeLast()
                shiftDown()
                return value
            }
        }
        
        public mutating func removeAt(_ index: Int) -> T? {
            guard index < self.elements.count else {
                return nil
            }
            
            let size = self.elements.count - 1
            if index != size {
                swap(&self.elements[index], &self.elements[size])
                shiftDown(index, heapSize: size)
                shiftUp(index)
            }
            
            return self.elements.removeLast()
        }    
    }
    
    extension Heap where T: Equatable {
        public func index(of element: T) -> Int? {
            return index(of: element, 0)
        }
        
        fileprivate func index(of element: T, _ i: Int) -> Int? {
            if i >= count {
                return nil
            }
            if isOrderedBefore(element, self.elements[i]) {
                return nil
            }
            
            if element == self.elements[i] {
                return i
            }
            if let j = index(of: element, self.leftChildIndex(ofIndex: i)) {
                return j
            }
            if let j = index(of: element, self.rightChildIndex(ofIndex: i)) {
                return j
            }
            
            return nil
        }
    }
    
    extension String {
        var asciiValueOfCharacter: Int {
            get {
                let value = self.unicodeScalars.filter{$0.isASCII}.first?.value ?? 0
                return Int(value) 
            }
        }
    }
    

Log in to reply
 

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