243 & 245. Shortest Word Distance i, iii,

243: https://leetcode.com/problems/shortest-word-distance/description/

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

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

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

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

双指针

    public int shortestDistance(String[] words, String word1, String word2) {
        int distance = Integer.MAX_VALUE;
        int index1 = -1;
        int index2 = -1;
        
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                index1 = i;
                if (index2 >= 0) {
                    distance = Math.min(distance, index1 - index2);
                }
            }
            
            if (words[i].equals(word2)) {
                index2 = i;
                if (index1 >= 0) {
                    distance = Math.min(distance, index2 - index1);
                }
            }
        }
        
        return distance;
    }

245. https://leetcode.com/problems/shortest-word-distance-iii/description/

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.

如果 word1 == word2，使用第二个 private function shortest(String[] words, String word) 就好。估计不是这道题目的考察点。看了题解，使用 flag 和 一个 function 实现。

还挺烦这种需要绕来绕去的逻辑的。下面是自己的题解：

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int distance = Integer.MAX_VALUE;
        int index1 = -1;
        int index2 = -1;
        boolean isSame = word1.equals(word2);
        
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                index1 = i;
                if (index2 >= 0) {
                    distance = Math.min(distance, index1 - index2);
                    if (isSame) {
                        int tmp = index1;
                        index1 = index2;
                        index2 = tmp;
                    }
                }
            }
            
            if (words[i].equals(word2)) {
                if (isSame && index2 >=0 ) {
                    continue;
                }
                index2 = i;
                if (index1 >= 0 && index1 != index2) {
                    distance = Math.min(distance, index2 - index1);
                }
            }
        }
        
        return distance;
    }
}

以下参考：http://www.cnblogs.com/grandyang/p/5192426.html

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int distance = Integer.MAX_VALUE;
        int index1 = -1;
        int index2 = -1;
        int tmpIndex = -1;
        boolean sameWord = word1.equals(word2);
        
        for (int i = 0; i < words.length; i++) {
            tmpIndex = index1;
            boolean found = false;
            
            if (words[i].equals(word1)) {
                index1 = i;
                found = true;
            }
            if (words[i].equals(word2)) {
                index2 = i;
                found = true;
            }
            
            if (found && index1 >= 0 && index2 >= 0) {
                if (!sameWord) {
                    distance = Math.min(distance, Math.abs(index1 - index2));
                } else if (tmpIndex >= 0) {
                    // boolean found 可以使用 (index1 > tmpIndex) 来代替
                    distance = Math.min(distance, index1 - tmpIndex);
                }
            }
        }
        
        return distance;
    }
}

使用一个变量来记录上一个位置。

更为优化的解法，不需要 tmpIndex。
我们并不需要变量t来记录上一个位置，我们将p1初始化为数组长度，p2初始化为数组长度的相反数，然后当word1和word2相等的情况，我们用p1来保存p2的结果，p2赋为当前的位置i，这样我们就可以更新结果了，如果word1和word2不相等，则还跟原来的做法一样

class Solution {
public:
    int shortestWordDistance(vector<string>& words, string word1, string word2) {
        int p1 = words.size(), p2 = -words.size(), res = INT_MAX;

        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1) p1 = word1 == word2 ? p2 : i;
            if (words[i] == word2) p2 = i;
            res = min(res, abs(p1 - p2));
        }

        return res;
    }
};