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.
这个也是比较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.