My Java Solution using embedded hashmap as a cache


  • 0
    L

    I use an embedded hash map to cache distance that has been asked before. And for new distance, use solution from problem 1 to calculate the result, and then store it in the cache

    public class WordDistance {
            private Map<String, Map<String, Integer>> cache;
            private String[] words;
            public WordDistance(String[] words) {
                cache = new HashMap<String, Map<String, Integer>>();
                this.words = words;
            }
        
            public int shortest(String word1, String word2) {
                // Make sure word1 < word2
                if(word1.compareTo(word2) > 0)
                {
                    String tmp = word1;
                    word1 = word2;
                    word2 = tmp;
                }
                
                if(cache.containsKey(word1) && cache.get(word1).containsKey(word2))
                {
                    return cache.get(word1).get(word2);
                }
                else
                {
                    int distance = shortestDistance(words, word1, word2);
                    if(!cache.containsKey(word1))
                    {
                        cache.put(word1, new HashMap<String, Integer>());
                    }
                    
                    cache.get(word1).put(word2, distance);
                    return distance;
                }
            }
            
            public int shortestDistance(String[] words, String word1, String word2) {
                int pos1 = -1;
                int pos2 = -1;
                int min = words.length;
                for(int i = 0; i < words.length; i++)
                {
                    if(words[i].equals(word1))
                    {
                        pos1 = i;
                    }
                    else if(words[i].equals(word2))
                    {
                        pos2 = i;
                    }
                    else
                    {
                        continue;
                    }
                    
                    if(pos1 != -1 && pos2 != -1)
                    {
                        min = Math.min(Math.abs(pos1 - pos2), min);
                    }
                }
                
                return min;
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.