Leetcode 126: Word Ladder II

I used a similar approach to Word Ladder I (leetcode 126), where I used BFS to go through all adjacent words (1 character different). The main difference is that I need to keep track of the whole path, which I do as an array in the queue rather than just one word. I also needed to delay marking used until the end of level because we can have multiple routes of the same size but have different beginnings. In order to not TLE I had to optimise the word matching for large word sets, where I used an unordered_map as a dictionary of the words and then I search every letter combination that is one character different.

My first attempt was too slow as it went through each word in wordList checking if the current word was one character different:
I optimised this for large wordLists to use a hashmap to search for all permutations of 1 character different strings, which passed the leetcode test cases:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.