CODEWITHSUNDEEP
python
Alice
Alice

Reputation: 1400

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

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

enter image description here

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?

Upvotes: 9

Views: 525

Answers (2)

Hamza
Hamza

Reputation: 6045

You can use levenshtein Distance (Credits: This Answer) as a metric to know the exact distance. From the Wikipedia page:

the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

As follows:

def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

then you can simply use levenshtein Distance to filter out pairs which are one character away from one another as:

new_list= []
mylist =  [beginWord].__add__(wordList)
for idx1, elem1 in enumerate(mylist):
    for idx2, elem2 in enumerate(mylist):
        if levenshteinDistance(elem1,elem2) == 1 and idx1 < idx2:
            new_list.append((elem1,elem2))
            
new_list

Which outputs:

[('hit', 'hot'),
 ('hot', 'dot'),
 ('hot', 'lot'),
 ('dot', 'dog'),
 ('dot', 'lot'),
 ('dog', 'log'),
 ('dog', 'cog'),
 ('lot', 'log'),
 ('log', 'cog')]

Then you can play around with this list to find out the shortest path. Everytime you have to simply search for the latter entry of the tuple in the hand to be the first entry of the next. You can add in the check for endword either in the distance logic or in the last part. ​

Upvotes: 1

Lucas
Lucas

Reputation: 395

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

Upvotes: 1

Related Questions