class Solution {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {

        var wordSet: Set<String> = Set<String>()

        wordList.forEach {
            wordSet.insert($0)
        }

        guard wordSet.contains(endWord) else {
            return 0
        }

        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
                }

                getNextSate(&nextQueue, currentWord, &visited, wordSet)
            }
            (queue, nextQueue) = (nextQueue, queue)
            depth += 1
        }
        return 0
    }

    func getNextSate(_ next: inout Queue<String>,_ currentWord: String,_ visited: inout Set<String>,_ dict: Set<String>) {
        let alphabetArray = Array("abcdefghijklmnopqrstuvwxyz".characters)
        for i in 0 ..< currentWord.characters.count {
            var chars = Array(currentWord.characters)
            let temp = chars[i]
            for j in 0 ..< alphabetArray.count {
                if temp == alphabetArray[j] {
                    continue
                }

                chars[i] = alphabetArray[j]
                let newWord = String(chars)
                if dict.contains(newWord) && !visited.contains(newWord) {
                    visited.insert(newWord)
                    next.enqueue(newWord)
                }
            }
        }
    }
}

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