https://leetcode.com/problems/word-ladder/

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

A 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
print(ladderLength("hot", "dog", ["hot","dog","dot"]))
print(ladderLength("a", "c", ["a","b","c"])) // 2