[LeetCode] Shortest Word Distance II

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.

Using a trie can definitely save some space especially when there are duplicate words in the list. But I think using a hashmap is more time-optimal since it has a constant look-up time. But trie requires O(n) to retrieve the list of indices where n is the size of the word. It’s like a trade-off between space and time.