Java - use map as cache, getting TLE, can't think of a good reason.


  • 0
    J
    public class WordDistance {
    private String[] words;
    private Map<String, Integer> cache;
    
    public WordDistance(String[] words) {
        this.words = words;
        cache = new HashMap<>();
    }
    
    public int shortest(String word1, String word2) {
    	if (word1.compareTo(word2) > 0)
    		return shortest(word2, word1);
    	String key = word1 + " " + word2;
    	if (cache.containsKey(key)) {
    		return cache.get(key);
    	} else {
    		int min = getShortestDistance(words, word1, word2);
    	    cache.put(key, min);
    	    return min;
    	}
    }
    
    private int getShortestDistance(String[] words, String word1, String word2) {
       	int pos1 = -1, pos2 = -1, shortest = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
        	if (words[i].equals(word1)) {
        		pos1 = i;
        	}
        	if (words[i].equals(word2)) {
        		pos2 = i;
        	}
        	if (pos1 != -1 && pos2 != -1) {
        		shortest = Math.min(shortest, Math.abs(pos1 - pos2));
        	}
        }
        return shortest;
    }
    

    }


Log in to reply
 

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