Two solutions to LeetCode 127 Word Ladder

Question

I am working on Word Ladder - LeetCode

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Approach 1: Breadth First Search

class Solution1:
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype step: int
        """
        visited = set()
        wordSet = set(wordList)
        
        queue = [(beginWord, 1)]
        
        while len(queue) > 0: #queue is not empty 
            word, step = queue.pop(0)
            #logging.debug(f"word: {word}, step:{step}")

            #base case 
            if word == endWord:
                return step #get the result.
            if word in visited: #better than multiple conditions later.
                continue
            #visited.add(word) # paint word as visited
            
            #traverse all the  variants 
            for i in range(len(word)):
                for j in range(0, 26): 
                    ordinal = ord('a') + j
                    next_word = word[0:i] + chr(ordinal) + word[i + 1:]
                    #logging.debug(f"changed_word: {next_word}")
                    if next_word in wordSet: 
                        queue.append((next_word, step + 1)) #contiue next stretch 
            visited.add(word) # paint word as visited
        
        return 0 

Runtime: 740 ms, faster than 22.79% of Python3 online submissions for Word Ladder.

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

Approach 2: Bidirectional Breadth First Search

class Solution2(object):
    def ladderLength(self, beginWord, endWord, wordList):
        #base case
        if (endWord not in wordList) or (not endWord) or (not beginWord) or (not wordList):
            return 0
        size = len(beginWord)
        word_set = set(wordList)    
        forwards, backwards = {beginWord}, {endWord}
        visited = set()
        step = 0
        while forwards and backwards:
            step += 1 #treat the first word as step 1
            if len(forwards) > len(backwards): 
                forwards, backwards = backwards, forwards #switch process
            #logging.debug(f"step: {step}, forwards: {forwards}, backwords: {backwards}")

            neighbors= set()   
            for word in forwards:#visit words on this level
                if word in visited: continue

                for i in range(size):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        next_word = word[:i] + c + word[i+1:]
                        if next_word in backwards: return step +  1 #terminating case
                        if next_word in word_set: neighbors.add(next_word)
                        #logging.debug(f"next_word{next_word}, step: {step}")
                visited.add(word) #add visited word as the final step 
            forwards = neighbors 
        #logging.debug(f"final: {step}")
        return 0

Runtime: 80 ms, faster than 98.38% of Python3 online submissions for Word Ladder.

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

TestCase

class MyCase(unittest.TestCase):
    def setUp(self):
        self.solution = Solution2()

    def test_1(self):
        beginWord = "hit" 
        endWord = "cog"
        wordList = ["hot","dot","dog","lot","log","cog"]
        #logging.debug(f"beginWord: {beginWord}\nendword:{endWord}\nwordList{wordList}")
        check = self.solution.ladderLength(beginWord, endWord, wordList)
        answer = 5
        self.assertEqual(check, answer)


    def test_2(self):
        beginWord = "hit" 
        endWord = "cog"
        wordList =  ["hot","dot","dog","lot","log"]
        check = self.solution.ladderLength(beginWord, endWord, wordList)
        answer = 0
        self.assertEqual(check, answer)

The memory usage in both solutions is bad.

Answer 1

            #traverse all the  variants 
            for i in range(len(word)):
                for j in range(0, 26): 
                    ordinal = ord('a') + j
                    next_word = word[0:i] + chr(ordinal) + word[i + 1:]
                    #logging.debug(f"changed_word: {next_word}")
                    if next_word in wordSet: 
                        queue.append((next_word, step + 1)) #contiue next stretch 

for i in range(len(word)): is poor practice. Prefer for i, ch in enumerate(word): or if you don't need the actual character:

for i, _ in enumerate(word):

You loop over 0-25 and construct the lowercase alphabet. You could just import ascii_lowercase from string.

            #traverse all the  variants 
            for i, _ in enumerate(word):
                for ch in string.ascii_lowercase: 
                    next_word = word[0:i] + ch + word[i + 1:]
                    #logging.debug(f"changed_word: {next_word}")
                    if next_word in wordSet: 
                        queue.append((next_word, step + 1)) #contiue next stretch

next_word = word[0:i] + ch + word[i + 1:] looks a little ugly. Let's use an f-string.

            #traverse all the  variants 
            for i, _ in enumerate(word):
                for ch in string.ascii_lowercase: 
                    next_word = f"{word[0:i]}{ch}{word[i + 1:]}"
                    #logging.debug(f"changed_word: {next_word}")
                    if next_word in wordSet: 
                        queue.append((next_word, step + 1)) #contiue next stretch

Really, we might just reduce this to a list comprehension and use that resulting list to extend queue.

            queue.extend([
                (next_word, step + 1)
                for i, _ in enumerate(word)
                for ch in string.ascii_lowercase
                for next_word in [f"{word[0:i]}{ch}{word[i + 1:]}"]
                if next_word in wordSet
            ])

Answer 2

Here are some general coding style suggestions.

Comments

Remove all commented-out code to reduce clutter:

#logging.debug(f"word: {word}, step:{step}")

#visited.add(word) # paint word as visited

Naming

It's a shame LeetCode does not adhere to the PEP 8 style guide, which recommends snake_case for function and variable names. This line:

def ladderLength(beginWord, endWord, wordList):

would be:

def ladder_length(begin_word, end_word, word_list):

In fact, wordList would be better as words.

Simpler

In Solution1, this line:

while len(queue) > 0: #queue is not empty 

is simpler as:

while len(queue): #queue is not empty 

This:

for j in range(0, 26): 

is simpler as:

for j in range(26): 

Efficiency

This expression is evaluated in nested loops:

ord('a')

Since it is a constant value, you can create a named constant at the top of the function before the while loop:

OFFSET = ord('a')

then use it inside the nested for loops:

ordinal = OFFSET + j

Documentation

The function docstring should be expanded to describe the algorithm.

Layout

In Solution1, lines like this:

if word in visited: continue

are better split into 2:

if word in visited:
    continue

The black program can be used to automatically reformat the code for you.