Skip to content

Instantly share code, notes, and snippets.

@boo1ean
Last active July 14, 2020 19:33
Show Gist options
  • Save boo1ean/8cc5155ce08ca2fd856f3f440f75d224 to your computer and use it in GitHub Desktop.
Save boo1ean/8cc5155ce08ca2fd856f3f440f75d224 to your computer and use it in GitHub Desktop.
function findLadders (beginWord, endWord, wordList) {
let results = []
let paths = [[beginWord]]
while (true) {
findPossibleMutations()
if (results.length) {
return results
}
if (!paths.length) {
return []
}
}
function findPossibleMutations () {
const newPaths = []
const toExclude = new Set()
for (const path of paths) {
const pathLastWord = path[path.length - 1]
for (const word of wordList) {
if (canMutate(pathLastWord, word)) {
toExclude.add(word)
if (word === endWord) {
results.push(path.concat([word]))
} else {
newPaths.push(path.concat([word]))
}
}
}
}
wordList = excludeItems(wordList, toExclude)
paths = newPaths
}
function canMutate (sourceWord, targetWord) {
let changes = 0
for (const i in sourceWord) {
if (sourceWord[i] === targetWord[i]) {
continue
}
changes++
}
return changes === 1
}
function excludeItems (array, toExclude) {
return array.filter(w => !toExclude.has(w))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment