Ac solution code


  • 1

    Special thanks to @qianzhige and @jeantimex

    The basic idea is using HashMap to store the position of each word in the array in constructor function. Then in 'shortest' function, use the method similar as merge sort to get the minimum difference between indices of word1 and word2.

    Time complexity of 'shortest' function = O(NumberOfWord1 + NumberOfWord2)

    Extra space = O(NumberOfWords)

    public class WordDistance {
    	private Map<String, List<Integer>>map; 
    	public WordDistance(String[] 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 LinkedList<Integer>());        	
            	map.get(words[i]).add(i);
            }
        }
        public int shortest(String word1, String word2) {
        	List<Integer> list1 = map.get(word1);
        	List<Integer> list2 = map.get(word2);
        	int i = 0, j = 0, res = Integer.MAX_VALUE;    	
            while (i < list1.size() && j < list2.size()) {
            	int index1 = list1.get(i);
            	int index2 = list2.get(j);        	        		
            	if (index1 < index2) {
            		i++;
            		res = Math.min(res, index2 - index1);
            	}
            	else { 
            		j++;
            		res = Math.min(res, index1 - index2);
            	}
            }
            return res;
        }
    }
    

Log in to reply
 

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