Checks for a Path in a List of Strings Given a Starting and Ending Point

Question

We are tasked to create a program that will check if there is a possible way of going from a starting string to an end string, given a list of strings with the same length. There is a catch, we can only go from the current string to the adjacent string if both strings only have one character that is different. If there is no possible path from the starting string to the end string, just print not possible but if there is, output the number of steps from the start to end.

Example:
li = ["booster", "rooster", "roaster", "coaster", "coasted"]
start = "roaster"
end = "booster"

Output: 3

li = ["booster", "rooster", "roaster", "coastal", "coasted"]
start = "roaster"
end = "coasted"

Output: none

I made an approach which manually checks if adjacent strings only have 1 character differences and returns the result based on these differences. Kinda slow if you ask me, given that the length of the list could be at most 100. Can you demonstrate a faster approach?

def checker(str1, str2, change = 0):

    for index, character in enumerate(str1):      # Traverses the whole
        if character != str2[index]:              # string and checks for   
            change+=1                             # character differences 
                                                  

    return True if change == 1 else False              # Only 1 character is different

li = ["booster", "rooster", "roaster", "coaster", "coasted"]
m = len(li)

for j in range(m): li.append(input())
start, end = input().split()

if end in li: endI = li.index(end)               # Gets end string index in the list
else:
    print("not possible")
    break

if start in li: startI = li.index(start)         # Gets start string index in the list
else:
    print("not possible")
    break

if startI < endI:                                # If start string comes first before 
                                                 # the end string, keep incrementing.

    while li[startI] != end and startI < m-1:

        if not checker(li[startI], li[startI+1]):
            print("not possible")
            break

        startI += 1

    print(abs(startI-(li.index(start)+1)))

else:                                            # Otherwise, keep decrementing.                                             

    while li[startI] != end and startI > 0:

        if not checker(li[startI], li[startI-1]):
            print("not possible")
            break

        startI -= 1

    print(abs(startI-(li.index(start)+1)))

If my approach is the fastest (which I highly doubt), I want to know if there are loopholes in my approach. Assume that the start and end strings can also be absent in the list given. Just print not possible if they are not in the list.

Answer 1

I hope that looks better:

import regex

def word_path(words, start, end):
    if end in words and start in words:
        endI = words.index(end)
        startI = words.index(start)
    else:
        return "not possible"

    step = 1 if startI <= endI else -1

    for index in range(startI, endI, step):
        if not regex.match("(%s){e<=1}" %li[index], li[index + step]):
            return "not possible"
    return abs(startI - endI) + 1

li = ["booster", "rooster", "roaster", "coastal", "coasted"]
start, end = input().split()
print(word_path(li, start, end))