Why use Map<String, Map<String, Integer>> will have TLE?


  • 0
    D

    here is my code:

    class WordDistance {
    Map<String, List<Integer>> map;
    String[] words;

    public WordDistance(String[] words) {
        this.words = words;
        map = new HashMap<String, List<Integer>>();
        for(int i = 0; i < words.length; i++){
            if(!map.containsKey(words[i])){
                map.put(words[i], new ArrayList<Integer>());
            }
            List<Integer> list = map.get(words[i]);
            list.add(i);
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        int dist = Integer.MAX_VALUE;
        
        for(int i = 0, j = 0; i < list1.size() && j < list2.size(); ){
            int p1 = list1.get(i);
            int p2 = list2.get(j);
            if(p1 < p2){
                dist = Math.min(dist, p2 - p1);
                i++;
            }else{
                dist = Math.min(dist, p1 - p2);
                j++;
            }
        }
        
        return dist;
    }
    

    }


Log in to reply
 

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