@@ -0,0 +1,2672 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.%0A * %3Cp%3E%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 * word1 and word2 may be the same and they represent two individual words in the 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%9Cmakes%E2%80%9D, word2 = %E2%80%9Ccoding%E2%80%9D, return 1.%0A * Given word1 = %22makes%22, word2 = %22makes%22, return 3.%0A * %3Cp%3E%0A * Note:%0A * You may assume word1 and word2 are both in the list.%0A * %3Cp%3E%0A * Company Tags: LinkedIn%0A * Tags: Array%0A * Similar Problems: (E) Shortest Word Distance, (M) Shortest Word Distance II%0A */%0Apublic class ShortestWordDistance3 %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,%0A     * and the two words are the same or previous word is not the same as the current one.%0A     * 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        boolean same = word1.equals(word2);%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 && (same %7C%7C !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 may be the same but indices are not.%0A     * i1 and i2 are the last seen positions for word1 and word2.%0A     * When word1 and word2 are the same,%0A     * i1 is the first position, i2 is the latest position.%0A     */%0A    public int shortestWordDistanceB(String%5B%5D words, String word1, String word2) %7B%0A        int i1 = -1;%0A        int i2 = -1;%0A        int shortest = Integer.MAX_VALUE;%0A        boolean same = word1.equals(word2);%0A        for (int i = 0; i %3C words.length; i++) %7B%0A            if (words%5Bi%5D.equals(word1)) %7B%0A                if (same) %7B%0A                    i1 = i2;%0A                    i2 = i;%0A                %7D else %7B%0A                    i1 = i;%0A                %7D%0A            %7D else if (words%5Bi%5D.equals(word2)) %7B%0A                i2 = i;%0A            %7D%0A            shortest = Math.min(shortest, Math.abs(i1 - i2));%0A        %7D%0A        return shortest;%0A    %7D%0A%0A%7D%0A

add shortest distance 3