Leetcode.com problem 127: "Word-Ladder-I"

James S. Plank

Mon Aug 15 00:45:51 EDT 2022

Problem Statement.
Success Rate (as of August, 2022): 36.2%
This is a "hard" problem.
ex-1-8.txt - A file for testing.
ex-2-6.txt - A file for testing.
ex-3-4.txt - A file for testing.
ex-4-7.txt - A file for testing.
ex-5-7.txt - A file for testing.
ex-6-4.txt - A file for testing.
ex-7-5.txt - A file for testing.
ex-8-5.txt - A file for testing.
ex-9-18.txt - A file for testing.
ex-a-0.txt - A file for testing.
ex-b-10.txt - A file for testing.
tests.sh: A testing script
answers.txt: Correct output to the testing script
A skeleton with my main() that you can use to test your answer.

In case Leetcode's servers are down

You are to write a method in the class Solution with the following prototype:

int ladderLength(string b, string e, vector<string>& wordList);

All of the strings (b, e and all the words in wordList) are the same size, between 1 and 10 characters.

Your job is to convert b to e by a sequence of "transformations." You can tranform a word x to a word y if y is in wordList, and x and y differ by exactly one character. Your goal is to convert b to e with a minimum number of transformations. Return that number plus one, if it's possible. If it's impossible, then return 0.

It's ok for b not to be in wordList. However, since the second word in a transformation has to be in wordList, e must be in wordList, or you'll return 0.

Constraints:

wordList will have at most 5000 words.
Each word in wordList is unique.
b doesn't equal e.
Leetcode restricts the letters to lower-case, but that's not important for your solution, so my tests have uppercase letters and numbers as well.

The testing program in skeleton.cpp reads b, then e, then all the words in wordList. So:

UNIX> echo hit cog hot dot dog lot log cog | ./a.out    # One sequence is hit -> hot -> dot -> dog -> cog
5
UNIX> echo hit cog hot dot dog lot log | ./a.out        # "cog" is not in wordList
0
UNIX>

In the example files, the second number is the answer, so:

UNIX> ./a.out < ex-1-8.txt
8
UNIX> ./a.out < ex-2-6.txt
6
UNIX>

Hints

I'm hoping that you can easily see that this is an unweighted shortest path problem. That means you can solve it with a breadth-first search. In the first example above, here's the graph in ASCII art:

hit -- hot -- dot -- dog
        |   /      /  |
        |  /      /   |
        | /      /    |
        |/      /     |
       lot -- log -- cog

So, step one should be to convert the word list into a graph:

Determine whether b and e are in the word list. If e is not, then return 0. If b is not, then put it at the end.
Obviously, each word will be a node on the graph. You'll be working with node numbers, which are the indices of wordList.
You should represent the graph as a vector of adjacency lists. Go ahead and declare and resize that variable.
Now build the adjacency list with a simple and slow algorithm: Test each pair of words, and determine whether they differ by one character. If so, append each node to the other node's adjacency list.
Test by printing the adjacency lists.

Here's the example above. You'll note that "hit" wasn't on the word list, so I appended it there. That's why it is node 6.

UNIX> echo hit cog hot dot dog lot log cog | ./a.out
 0 hot:  1  3  6
 1 dot:  0  3  2
 2 dog:  4  5  1
 3 lot:  0  1  4
 4 log:  2  5  3
 5 cog:  2  4
 6 hit:  0
UNIX>

Now, write the BFS. If you're not experienced yet with writing a BFS, this is a good time to get experience. The CS302 lecture notes for BFS are here.

You can now test your answer on the examples. The first 8 will run quickly, but the last three will be too slow.

Making your program fast enough

The reason your program is too slow is the way that you are creating the adjacency lists. It is O(n²), where n is the size of the word list. Since n can be as big as 5000, O(n²) won't do.

It's not a bad idea to pause for a moment, and try to think of how to create the adjacency lists faster. Think about how you can employ a map. Scroll down to see my approach.

Here was my approach. Let's first look for all words who differ only by the first character. For each word in the list, create a string which is the word missing the first character. If two words differ by only the first character, then their strings will match! So, insert each of these strings into the map. The val part of the map will be an array of node indices. In the example above, the map will be:

{ ("it",[6]), ("og",[2,4,5]), ("ot",[0,1,3]) }

Now you can put the following nodes onto the adjacency list:

From "og": (2,4), (2,5), (4,2), (4,5), (5,2), (5,4)
From "ot": (0,1), (0,3), (1,0), (1,3), (3,0), (3,1)

Now, do this for the second character, then the third, etc. Clear the map each time before you start.

What's the running time complexity? Let's let m be the word size. It's O(m² n log n). Why m²? Because you run the outer loop for m iterations, and then creating the string is also O(m). Since m is capped at 10, this is much faster than the O(n²) loop above.

That should give you enough tools to solve this and have it be fast enough!