Exhaustively get all the possible combinations of a word of three lettters

Question

I am working on a leetcode problem "wordLadder"

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.

my solution

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        visited = set()
        wordSet = set(wordList)

        queue = [(beginWord, 1)]

        while len(queue) > 0:
            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

            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))
            visited.add(word) # paint word as visited

        return 0 

To exhaust all the possible combination of a word

I read the discussion area, all employed the slice techniques

next_word = word[0:i] + chr(ordinal) + word[i + 1:]

Is there other solutions to handle the problem?

Answer 1

This is a classical networking problem. What you should do is generate a square Matrix with dimensions equal to the number of words in your dictionary. Then fill the matrix with ones wherever the words are a one letter transformation towards each other i.e.

network['hot']['not'] = 1

all other cells need to be 0.

Now you defined your network, and you can use a shortest path algorithm like Dijkstra in order to solve your Problem