I just tried out this Leetcode problem as part of this long-term growth commitment I’ve agreed with both Grace and Isabel for.
How would you folks actually approach the problem?
When I tried it out, eventually I got to using a hash map with words as the keys and array lists of integers holding the indices, then just using linear search to find the shortest distance between them. It turns out that’s the most common approach used according to the solution and the discussion board.
I did thought of an optimization in terms of space for the hash map, but not for runtime: instead of using strings as the key, I replace the entire hash map with a trie where each node contains a nullable array list reference to the indices. With this, I would not be allocating memory over a duplicated sequence of characters from one word to the next. For instance, if I have the words “tea,” “tee,” and “ten”, a trie saves me from having to allocate the space to store “te” three times.