245. Shortest Word Distance III ----M

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.

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “makes”, word2 = “coding”
Output: 1

Input: word1 = "makes", word2 = "makes"
Output: 3

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

A:

************  第二遍**************************

与II的唯一区别，就是增加了  if (a==b) continue  这一句

class Solution {
public:
    int shortestWordDistance(vector<string>& words, string word1, string word2) {
        vector<int> V1;
        vector<int> V2;
        for(int i = 0;i<words.size();i++){
            if(words[i] == word1){
                V1.push_back(i);
            }
            if(words[i] == word2){
                V2.push_back(i);
            }
        }
        int res = INT_MAX;
        for(int i1=0, i2=0;i1<V1.size();i1++){
            int a = V1[i1];
            int b = V2[i2];
            if(a==b)
                continue;
            res = min(res, abs(a-b));
            if(a>b){
                // increase b
                if(i2+1<V2.size()){
                    i2++;
                    i1--;
                }
            }
        }
        return res;
    }
};

*************笨办法， 从低到高，计算每一个可能的步长并对比**********

public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        for(int step = 1; step<words.length;step++){
            for(int i =0;i + step < words.length; i++){
                boolean bln1=words[i].equals(word1) && words[i+step].equals(word2);
                boolean bln2=words[i].equals(word2) && words[i+step].equals(word1);
                if(bln1 || bln2)
                    return step;
            }
        }
        return -1;
    }
}

*******  更快速 ***********但只是一遍的****************
每次跟随检验， 利用的特性是:  每次往前一个新的string，我们只记录最近发现的word1 ,和 word2.

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