127. Word Ladder

문제의 조건에서 중요한 점

• 시작 단어는 리스트에 들어가지 않는다.
• 한번에 하나의 단어만 바뀔 수 있다.
• 끝 단어가 단어리스트에 존재해야만 한다. 없을시 0 리턴

bfs인데 다음 원소가 조건에 따라 달라지는 형태의 bfs 한번의 bfs에서 될 수 있는 모든 단어를 찾아야한다. 따라서 for문의 첫번째는 단어 두번째는 모든 알파벳에 대하여 탐색한다. 그리고 변할 수 있는 단어를 찾으면 그 단어를 set에서 지운다.

const ladderLength = function (beginWord, endWord, wordList) {
  // 없으면 컷.
  if (!wordList.includes(endWord)) return 0

  const wordSet = new Set(wordList)
  let queue = [beginWord]
  let steps = 1

  while (queue.length) {
    const next = []
    for (let word of queue) {
      if (word === endWord) return steps

      for (let i = 0; i < word.length; i++) {
        for (let j = 0; j < 26; j++) {
          const newWord =
            word.slice(0, i) + String.fromCharCode(j + 97) + word.slice(i + 1)
          if (wordSet.has(newWord)) {
            next.push(newWord)
            wordSet.delete(newWord)
          }
        }
      }
    }
    queue = next
    steps++
  }
  return 0
}

 

Set.prototype.delete() 기억하기