O(n+m) 168ms Accepted Java Soln


  • 0
    R
    public class WordDistance {
    
            private Map<String, LinkedList<Integer>> wordMap = new HashMap<>();
            private int size;
    
            public WordDistance(String[] words) {
                size = words.length+1;
                for(int i=0; i<words.length; i++){
                    if(!wordMap.containsKey(words[i])){
                        wordMap.put(words[i], new LinkedList<Integer>());
                    }
                    wordMap.get(words[i]).addLast(i);
                }
            }
    
            public int shortest(String word1, String word2) {
                LinkedList<Integer> w1list = wordMap.get(word1);
                LinkedList<Integer> w1listC = (LinkedList<Integer>)w1list.clone();
                LinkedList<Integer> w2list = wordMap.get(word2);
                LinkedList<Integer> w2listC = (LinkedList<Integer>)w2list.clone();
                boolean lastElemFromW1 = false;
                int min = Integer.MAX_VALUE;
                int N = size;
                int w1 = N, w2 = N;
                while(!w1listC.isEmpty() && !w2listC.isEmpty()){
                    if(w1listC.peek() < w2listC.peek()){
                        w1 = w1listC.removeFirst();
                        if(!lastElemFromW1){
                            min = Math.min(min, Math.abs(w1-w2));
                        }
                        lastElemFromW1 = true;
                    }
                    else{
                        w2 = w2listC.removeFirst();
                        if(lastElemFromW1){
                            min = Math.min(min, Math.abs(w1-w2));
                        }
                        lastElemFromW1 = false;
                    }
                }
                if(lastElemFromW1 && !w2listC.isEmpty()){
                    w2 = w2listC.removeFirst();
                    min = Math.min(min, Math.abs(w1-w2));
                }
                if(!lastElemFromW1 && !w1listC.isEmpty()){
                    w1 = w1listC.removeFirst();
                    min = Math.min(min, Math.abs(w1-w2));
                }
                return min;
            }
        }
    

Log in to reply
 

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