4
\$\begingroup\$

I was given this problem in an interview.

Given two words source and target, and a list of words words, find the length of the shortest series of edits that transforms source to target. Each edit must change exactly one letter at a time, and each intermediate word (and the final target word) must exist in words.

If the task is impossible, return -1.

Examples:

source = "bit"
target = "dog"
words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

Output: 5

Explanation: bit -> but -> put -> pot -> pog -> dog has 5 transitions.

source = "no"
target = "go"
words = ["to"]

Output: -1

def one_letter_difference(current_word, next_word):
      count = 0
      for i in range(len(current_word) -1):

        if current_word[i] != next_word[i]:
          count += 1;
      if count == 1:
        return True
      else:
        return False

    def shortestWordEditPath(source, target, words):
      """
        @param source: str
        @param target: str
        @param words: str[]
        @return: int

      Input: source = "bit", target = "dog"
      words = ["but", "put", "big", "pot", "pog", "dog", "lot"]

      Output: 5
      explanation: 
                 1  ->  1   ->   1  ->    1  ->     1
      (source) bit -> but -> put -> pot -> pog -> dog (target) 
      has minimum of 5 transitions    
        """
      graph = {}

      for i in range(-1, len(words)):
        if i == -1:
          current_word = source
        else:
          current_word = words[i]
        graph[current_word] = []
        for word in range(len(words)):
          next_word = words[word]
          if one_letter_difference(current_word, next_word):
            graph[current_word].append(next_word)

      #perform BFS
      queue = collections.deque()
      seen = set() # visited words
      queue.append([source, 1])
      seen.add(source)

      while len(queue) > 0:
        current, distance = queue.popleft()
        if current == target: return distance
        for neighbor in graph[current]:
          if neighbor not in seen:
            queue.append([neighbor, distance +1])
            seen.add(neighbor)
      return -1

    source = "bit"
    target = "dog"
    words = ["but", "put", "big", "pot", "pog", "dog", "lot"]
    test = shortestWordEditPath(source, target,words)
    print(test)
\$\endgroup\$
2
\$\begingroup\$

Let's start with the good:

  • You documented your public API!
  • You used decently descriptive variable names
  • You somewhat have a test case
  • Your use of a dictionary is resourceful here. No need for some fancy Node class.
  • You separated out some of the functionality to make the algorithm easier to reason about (checking if words are 1 edit distance apart)

Here are some things I noticed that perhaps the interviewer did as well:

  • Your formatting is inconsistent. PEP8 your code (4 space indents, space around operators).
  • You mix snake_case and camelCase. Python typically prefers snake_case.
  • You didn't document your internal function (not the end of the world, but it is a nice touch)
  • You didn't indicate that your internal function was private by prefixing it with a _ (my policy is always if it doesn't have a leading _ it must be documented)
  • if count == 1: return True else: return False would concern me as an interviewer as it demonstrates that you may not understand boolean expressions. return count == 1 would work. But this additionally would pose another concern for me. Namely, one_letter_difference could be a short circuited function, but you did not implement it this way. I also would name it differently, one_letter_difference doesn't say what it does. Also, this function does not care about current or next words, so don't call them that. We also typically try to avoid indexing in Python. You should use zip here. And not to pile on, but this function is also probably not correct. You should have test cases for it. I believe that dog to doge should be an edit distance of 1 as well. With that in mind:
def _is_one_edit_apart(word_a, word_b):
    if abs(len(word_a) - len(word_b)) > 1:
        # It is impossible for words differing by 2 or more letters in length to
        # be just one edit apart
        return False

    if len(word_a) != len(word_b):
        shorter_word, longer_word = \
            (word_a, word_b) if len(word_a) < len(word_b) else (word_b, word_a)

        if longer_word.startswith(shorter_word) or longer_word.endswith(shorter_word):
            # The shorter word is a prefix or a suffix of the longer and
            # they differ by 1 character in length, so they are 1 edit apart
            return True

    num_edits = 0

    # We know that word_a and word_b are the same length, so zip won't truncate
    for a, b in zip(word_a, word_b):
        if a != b:
            num_edits += 1
            if num_edits > 1:
                return False

    return num_edits == 1

Note that you could also get clever here and make the edits a bit more succinct: num_edits = sum(1 for a, b in zip(word_a, word_b) if a != b). This is up to you. This certainly reads better. The approach above likely performs better because it short circuits (stops when it finds more than 1 edit).

  • Your graph construction is weird. range(-1, len(words)) seems like it could lead to trouble if you aren't careful. Generally, prefer for word in words. It seems like you add the edges to your graph for the current_word twice as a result of this.
  • Prefer for word in words to for word in range(len(words)). This may indicate to an interviewer that you don't understand Python iterators or common patterns. This could also be a comprehension (and probably should be a tuple since edges can't change): graph[word] = tuple(other_word for other_word in words if _is_one_edit_apart(word, other_word))
  • You should probably pull your BFS out into a helper function. It is used in your algorithm. It is not part of your algorithm. This way you can test it separately.
  • BFS is also probably not the best approach here. Dijkstra's is more suitable because it can find the shortest path between two nodes (we can just assume the edges indicate edit distance and are all cost 1).
  • queue.append([neighbor, distance +1]) should be a tuple not a list. You aren't going to mutate it. This would likely concern an interviewer.
  • This is part of the question, but I don't like returning -1 for error. If you forget to handle this, this could lead to a problem (say you try to do math on the distance and assume it's always positive). You should be raising some sort of error. If I was asked to do something this silly, I would probably write my own function that raises and then provide an alternate API for this use case which wraps this function and converts the exception to a -1 out of principle.
  • unittest your code. Don't just throw a print statement and manually verify! And test all the pieces! This is why you separate out the one edit distance check and the BFS (well, Dijkstra's)

There's another larger problem in my mind, which isn't specified by the question, but it's the kind of question that I'd expect an engineer who encountered this problem to explore: what is the use case? Is this is one off (eg. are we using different word lists with every query)? If the word list is reused, this algorithm is inefficient, because it constructs a graph for each query. If the word list remains the same, then you should build the graph up once and then only do Dijkstra's for each query. I would implement this with a class the encapsulates the built graph and provide external API to query for edit distances. Then you could provide a function that uses this class for a one off query (where the words list is unique--never to be used again) to satisfy this interview question.

There is also an optimization you can make in constructing the graph. It is apparent from my revised _is_one_edit_apart. Namely, words can only be one edit apart if they are the same length or differ in length by only 1 character. So, when building the graph you can take this into account. Take all of the words group them by length. Then to build the part of the graph for length 1 words, you only have to consider length 1 or length 2 words. For length 2 words you have to consider length 1, 2, and 3 words. Etc. You original approach is always O(n^2). This is still worst case O(n^2) but will average much better than this given a decent distribution of word lengths.

\$\endgroup\$
  • 1
    \$\begingroup\$ Oops, indeed I did! \$\endgroup\$ – Bailey Parker Mar 26 at 10:13
  • \$\begingroup\$ i am confused by what you did? \$\endgroup\$ – NinjaG Apr 11 at 2:59
  • \$\begingroup\$ I made a math mistake (I believe) and someone pointed it out, but they deleted their comment. \$\endgroup\$ – Bailey Parker Apr 11 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.