Leetcode | Word Ladder II

In preparation for fulltime interviews in the coming months I’ve been doing a lot of leetcode questions. I have many feelings on whether or not this is the best way to determine someone’s coding abilities, but that’s for a different post. I wanted to share my struggles with one particular question: word ladder ii. I’m not going to paste the prompt here, so if you’re reading this maybe read the prompt first.

Why did I find this one particularly challenging? I’m not sure, exactly. I know all of the strategies involved, I’ve done similar questions before, I know all of the data structures… I think just the size of the problem perhaps got to me. Anyway, I’m going to go over a few failed attempts of mine (they both worked, just timed out on some test cases) followed by a working solution. I’ll conclude with some final thoughts.

Solution 1

My first mistake was I just started coding. This usually ends poorly for me with these types of questions. I tried to come up with a strategy but since I was timing myself, I figured the solution would unfold as I went. This is what my first code looked like:

The basic strategy here was to do a DFS which generated possibilities on the fly (potential next words) and stopped once we found the endWord. Once I did, I saved the min_so_far to save how deep in the graph we are. This way, we never go deeper than that and can cut off searches early. Unfortunately, this had many flaws. Some include:

  • DFS instead of BFS. DFS means that we could end up searching deeper than we need to. More on this later.
  • Not using good data structures. Everything is saved as an array here. For searching repeatedly or checking for existence dictionaries and sets would work better.
  • Overly recursive. Sure, the recursive solution may seem sexy but it’s rarely the fastest and in this case was the final nail in the coffin of this solution.

To be clear, this solution worked it was just very slow.

Solution 2

This solution DID perform much better, but unfortunately it was just adding enhancements to my already poor code. Here is what it looked like:

OhhHHhh! Look how shiny and modular everything is! He even added a Node class. Unfortunately, at this point I didn’t realize that the problem was DFS and so even though this performed way better, it still wasn’t good enough to pass the tests on leetcode. TBH, in an interview this would probably fly because the code is sound. But, again, missing the benefits of BFS here is a silly mistake that wouldn’t have been good in an interview.

Solution 3

At this point I was depressed, sad, and stuck. So, I looked at the discussion section and found a great python solution that I adapted to get things working finally. Here is the code:

The author had a couple of good strategies which I will consider for future problems. Namely:

  • Instead of calculating hamming distance with every word in the wordList, just iterate through every letter. This caps the number of combinations you try at each level and works well when your words are small and your wordLists are huge.
  • BFS first to generate the graph and only then DFS to search the graph. BFS for graph generation means that we will ALWAYS find the shortest distance and will never search deeper than that. There might be other solutions ending at that layer, but we will never search below that.
  • set()‘s and {}‘s save the day here. Lookup and existence checking are much faster than arrays for these data structures.

Now running this code on even the largest dataset in the test scenarios yields:

I’d call that a victory!

Complexity Analysis

#TODO

Leave a Reply

Your email address will not be published. Required fields are marked *

*