@@ -0,0 +1,2437 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0A/**%0A * Given a list of words and two words word1 and word2, return the shortest distance between these two words in the%0A * list.%0A * %3Cp%3E%0A * For example,%0A * Assume that words = %5B%22practice%22, %22makes%22, %22perfect%22, %22coding%22, %22makes%22%5D.%0A * %3Cp%3E%0A * Given word1 = %E2%80%9Ccoding%E2%80%9D, word2 = %E2%80%9Cpractice%E2%80%9D, return 3.%0A * Given word1 = %22makes%22, word2 = %22coding%22, return 1.%0A * %3Cp%3E%0A * Note:%0A * You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.%0A * %3Cp%3E%0A * Company Tags: LinkedIn%0A * Tags: Array%0A * Similar Problems: (M) Shortest Word Distance II, (M) Shortest Word Distance III%0A */%0Apublic class ShortestWordDistance %7B%0A%0A    /**%0A     * Array. Only one index.%0A     * Remember the previous index word1 or word2 seen.%0A     * Iterate through the array.%0A     * If we find either word1 or word2.%0A     * If previous index is initialized, and previous word is not same as the current one, update min.%0A     * Then we update previous index.%0A     */%0A    public int shortestWordDistance(String%5B%5D words, String word1, String word2) %7B%0A        int prevIndex = -1;%0A        int min = words.length;%0A        for (int i = 0; i %3C words.length; i++) %7B%0A            if (words%5Bi%5D.equals(word1) %7C%7C words%5Bi%5D.equals(word2)) %7B%0A                if (prevIndex != -1 && !words%5BprevIndex%5D.equals(words%5Bi%5D)) %7B%0A                    min = Math.min(i - prevIndex, min);%0A                %7D%0A                prevIndex = i;%0A            %7D%0A        %7D%0A        return min;%0A    %7D%0A%0A    /**%0A     * Array. Two indices.%0A     * Words can have duplicates, so we cannot use a map directly.%0A     * The distance between is abs(index1 - index2).%0A     * We can update this distance every time index1 or index2 is updated.%0A     * Then we store the minimum among these values.%0A     */%0A    public int shortestDistanceB(String%5B%5D words, String word1, String word2) %7B%0A        int i1 = -1;%0A        int i2 = -1;%0A        int shortest = Integer.MAX_VALUE;%0A        for (int i = 0; i %3C words.length; i++) %7B%0A            if (words%5Bi%5D.equals(word1)) %7B%0A                i1 = i;%0A                if (i2 != -1) %7B%0A                    shortest = Math.min(shortest, Math.abs(i1 - i2));%0A                %7D%0A            %7D%0A            if (words%5Bi%5D.equals(word2)) %7B%0A                i2 = i;%0A                if (i1 != -1) %7B%0A                    shortest = Math.min(shortest, Math.abs(i1 - i2));%0A                %7D%0A            %7D%0A        %7D%0A        return shortest;%0A    %7D%0A%0A%7D%0A

add shortest word distance