package legacy_code.Problem241To250;

public class Shortest_Word_Distance_III {

    /**
     * 245. Shortest Word Distance III
     * This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

     Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

     word1 and word2 may be the same and they represent two individual words in the list.

     For example,
     Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

     Given word1 = “makes”, word2 = “coding”, return 1.
     Given word1 = "makes", word2 = "makes", return 3.

     Note:
     You may assume word1 and word2 are both in the list.
     */

    /**
     * Solution:
     * Depends on ShortestWordDistance, diff is a diff way to calculate the distance when word1.equals(word2), need to calculate i - index1, and then update index1 to i
     * For the code, could integrate equals and not equals into one for loop, like
     * if (word1.equals(word2)) else, but this will make extra n times compare will have more time complexity, so check word1.equals(word2) once
     *
     * Time: O(n)
     * Space: O(1)
     */

    public int shortestWordDistance(String[] words, String word1, String word2) {
        //If index1 or index2 is -1, means haven't found a matched word
        int index1 = -1;
        int res = Integer.MAX_VALUE;
        if (word1.equals(word2)) {
            for (int i = 0; i < words.length; i++) {
                if (words[i].equals(word1)) {
                    if (index1 != -1) res = Math.min(res, Math.abs(i - index1));
                    index1 = i;
                }
            }
        } else {
            int index2 = -1;
            for (int i = 0; i < words.length; i++) {
                if (words[i].equals(word1)) index1 = i;
                else if (words[i].equals(word2)) index2 = i;
                //If word1 and word2 found at least once, update the res
                if (index1 != -1 && index2 != -1) res = Math.min(res, Math.abs(index1 - index2));
            }
        }
        return res;
    }

}

@@ -74,16 +74,79 @@
 _III %7B%0A%0A
+    //TAG: LinkedIn%0A    //TAG: array%0A    //Difficulty: Medium%0A%0A
     /**%0A
@@ -1374,69 +1374,92 @@
   //
-If index1 or
+when not find any word,
  index
-2 is
+ =
  -1, m
-eans haven't found a matched word
+ax distance (variable min) will be words.length
 %0A   
@@ -1476,267 +1476,193 @@
 ndex
-1
  = -1
-;%0A        int res = Integer.MAX_VALUE;%0A        if (word1.equals(word2)) %7B%0A            for (int i = 0; i %3C words.length; i++) %7B%0A                if (words%5Bi%5D.equals(word1)) %7B%0A                    if (index1 != -1) res = Math.min(res, Math.abs(i - index1));
+, min = words.length;%0A        for (int i = 0; i %3C words.length; i++) %7B%0A            //If i met any word1 or word2%0A            if (words%5Bi%5D.equals(word1) %7C%7C words%5Bi%5D.equals(word2)) %7B
 %0A   
@@ -1678,236 +1678,206 @@
     
-   
+//If
  index
-1 = i;%0A                %7D%0A            %7D%0A        %7D else %7B%0A            int index2 = -1;%0A            for (int i = 0; i %3C words.length; i++) %7B%0A                if (words%5Bi%5D.equals(word1)) index1 = i;%0A                else if (
+ at some word and (word1 == word2 or if not equal, not at the same word record before, means%0A                // the other word)%0A                if (index != -1 && (word1.equals(word2) %7C%7C !
 word
@@ -1896,23 +1896,21 @@
 word
-2)) 
+s%5B
 index
-2 = i;
+%5D))) %7B
 %0A   
@@ -1926,161 +1926,87 @@
     
-//If word1 and word2 found at least once, update the res%0A                if (index1 != -1 && index2 != -1) res = Math.min(res, Math.abs(index1 - index2))
+    min = Math.min(min, i - index);%0A                %7D%0A                index = i
 ;%0A  
@@ -2042,19 +2042,19 @@
  return 
-res
+min
 ;%0A    %7D%0A

245. Shortest Word Distance III