LeetCode: 127. Word Ladder

wordLadder.swift

class Solution {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
    
        var wordSet: Set<String> = Set(wordList)
        
        guard wordSet.contains(endWord) else {
            return 0
        }
        
        // Lookup table for neighbors
        var neighborMap = [String: Set<String>]()
        
        neighborMap[beginWord] = beginWord.neighborsIn(wordSet)
        
        wordSet.forEach { word in
            word.neighborsIn(wordSet).forEach { key in
                if neighborMap[key]?.insert(word) == nil {
                    neighborMap[key] = [word]
                }
            }
        }
        
        var visited: Set<String> = [beginWord]
        var queue: Queue<String> = Queue<String>()
        queue.enqueue(beginWord)
        
        var depth = 1
        
        while !queue.isEmpty {
            var nextQueue: Queue<String> = Queue<String>()
            while let currentWord = queue.dequeue() {
                if currentWord == endWord {
                    return depth
                }
                
                let nextWords = neighborMap[currentWord]!
                for neighbor in nextWords {
                    if !visited.contains(neighbor) {
                        visited.insert(neighbor)
                        nextQueue.enqueue(neighbor)
                    }
                }
                
                //getNextSate(&nextQueue, currentWord, &visited, wordSet)
            }
            (queue, nextQueue) = (nextQueue, queue)
            depth += 1
        }
        return 0
    }
}

extension String {
    // Return a Set of all possible neighbors
    func neighborsIn(_ words: Set<String>) -> Set<String> {
        var neighbors = Set<String>()
        
        let alphabetArray = Array("abcdefghijklmnopqrstuvwxyz".characters)
        for i in 0 ..< self.characters.count {
            var chars = Array(self.characters)
            let temp = chars[i]
            for j in 0 ..< alphabetArray.count {
                // skip origin word
                if temp == alphabetArray[j] {
                    continue
                }
                
                chars[i] = alphabetArray[j]
                let newWord = String(chars)
                if words.contains(newWord) {
                    neighbors.insert(newWord)
                }
            }
        }
        
        return neighbors
    }
}

struct Queue<T> {
    private var array: [T]
    var isEmpty: Bool {
        return array.count == 0
    }
        
    var count: Int {
        return array.count
    }
        
    init() {
        array = []
    }
        
    mutating func enqueue(_ element: T) {
        array.append(element)
    }
        
    mutating func dequeue() -> T? {
        if isEmpty { return nil }
        
        return array.removeFirst()
    }
    
    func peek() -> T? {
        return array.first
    }
}