# Word ladder implementation in Swift

This post contains the implementation for the leetcode problem shown in the link above.

transformation sequence from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:

• Every adjacent pair of words differs by a single letter.
• Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
• `sk == endWord`

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return the number of words in the shortest transformation sequence from `beginWord` to `endWord`, or `0` if no such sequence exists.

Example 1:

```Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
```

Example 2:

```Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
```

Constraints:

• `1 <= beginWord.length <= 10`
• `endWord.length == beginWord.length`
• `1 <= wordList.length <= 5000`
• `wordList[i].length == beginWord.length`
• `beginWord``endWord`, and `wordList[i]` consist of lowercase English letters.
• `beginWord != endWord`
• All the words in `wordList` are unique.
``````func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
let characters = "abcdefghijklmnopqrstuvwxyz"
var queue: [String] = [String]()
var set: Set<String> = Set<String>()
// 1. insert all words into a set
for wordList in wordList {
set.insert(wordList)
}
// 2. add the begin word to the queue
queue.insert(beginWord, at: 0)
// 3. set the depth to 1
var depth = 0
// 4. start a depth first search of the words using the queue
while !queue.isEmpty {
let word = queue.remove(at: 0)
depth += 1
print("\(word) \(depth)")
// 5. replace each character in the begin word with all the alphabets
for i in 0 ..< word.count {
let alternate = word
for character in characters {
// 6. replace ith character in begin word, with the character in the alphabet
let replaced = alternate.replacingCharacters(in: alternate.index(alternate.startIndex, offsetBy: i) ... alternate.index(alternate.startIndex, offsetBy: i), with: String(character))
if replaced == word {
// 6a. if the starting word is the same as the replaced word
// e.g. hit [hit, sit] hit and hit are the same, don't need to replace
continue
}
if replaced == endWord {
// 7. exit here
return depth+1
}
if set.contains(replaced) {
// 8. remove this word from the set and add it to the queue
set.remove(replaced)
queue.append(replaced)
}
}
}
}
return 0
}

print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"])) // 5
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log"])) // 0