212 - 127 单词接龙

题目

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1. 每次转换只能改变一个字母。

2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。

• 所有单词具有相同的长度。

• 所有单词只由小写字母组成。

• 字典中不存在重复的单词。

• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2:

输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

解答

应该是通过找相似度，来一个个转换。但也要记一下换过的单词，不然会来回倒腾

https://leetcode.com/problems/word-ladder/discuss/157376/Python-(BFS)-tm

每个字都换一遍26个字母，来判断能不能到下一个字

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        import collections
        import string
        arr = set(wordList)
        q = collections.deque([(beginWord, 1)])
        visited = set()
        alpha = string.ascii_lowercase
        while q:
            word, length = q.popleft()
            if word == endWord:
                return length
            for i in range(len(word)):
                for ch in alpha:
                    new_word = word[:i]+ch+word[i+1:]
                    if new_word in arr and new_word not in visited:
                        q.append((new_word, length+1))
                        visited.add(new_word)
        return 0

Runtime: 560 ms, faster than 18.25% of Python3 online submissions for Word Ladder.

Memory Usage: 13.6 MB, less than 96.55% of Python3 online submissions for Word Ladder.

https://leetcode-cn.com/problems/word-ladder/solution/127-dan-ci-jie-long-by-alexer-660/

这个也是比较26字母，不过是用ascii码进行比较的。

var ladderLength = function(beginWord, endWord, wordList) {
  let wordListSet = new Set(wordList)
  if (!wordListSet.has(endWord)) {
    return 0
  }
  let beginSet = new Set()
  beginSet.add(beginWord)
  let endSet = new Set()
  endSet.add(endWord)
  let level = 1

  while (beginSet.size > 0) {
    let next_beginSet = new Set()
    for (let key of beginSet) {
      for (let i = 0; i < key.length; i++) {
        for (let j = 0; j < 26; j++) {
          let s = String.fromCharCode(97 + j)
          if (s != key[i]) {
            let new_word = key.slice(0, i) + s + key.slice(i + 1)
            if (endSet.has(new_word)) {
              return level + 1
            }
            if (wordListSet.has(new_word)) {
              next_beginSet.add(new_word)
              wordListSet.delete(new_word)
            }
          }
        }
      }
    }
    beginSet = next_beginSet
    level++
    if (beginSet.size > endSet.size) {
      [beginSet, endSet] = [endSet, beginSet]
    }
  }
  return 0
};

Runtime: 108 ms, faster than 98.27% of JavaScript online submissions for Word Ladder.

Memory Usage: 43.2 MB, less than 28.57% of JavaScript online submissions for Word Ladder.