Shortest Word Distance

// Time:  O(n)
// Space: O(1)

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int dist = INT_MAX;
        for (int i = 0, index1 = -1, index2 = -1; i < words.size(); ++i) {
            if (words[i] == word1) {
                index1 = i;
            } else if (words[i] == word2) {
                index2 = i;
            }
            if (index1 != -1 && index2 != -1) {
                dist = min(dist, abs(index1 - index2));
            }
        }
        return dist;
    }
};

// Time:  ctor: O(n), shortest: O(a + b), a, b is occurences of word1, word2
// Space: O(n)

class WordDistance {
public:
    WordDistance(vector<string> words) {
        for (int i = 0; i < words.size(); ++i) {
            wordIndex[words[i]].emplace_back(i);
        }
    }

    int shortest(string word1, string word2) {
        const vector<int>& indexes1 = wordIndex[word1];
        const vector<int>& indexes2 = wordIndex[word2];

        int i = 0, j = 0, dist = INT_MAX;
        while (i < indexes1.size() && j < indexes2.size()) {
            dist = min(dist, abs(indexes1[i] - indexes2[j]));
            indexes1[i] < indexes2[j] ? ++i : ++j;
        }
        return dist;
    }

private:
    unordered_map<string, vector<int>> wordIndex;
};

// Time:  O(n)
// Space: O(1)

class Solution {
public:
    int shortestWordDistance(vector<string>& words, string word1, string word2) {
        int dist = INT_MAX;
        for (int i = 0, index1 = -1, index2 = -1; i < words.size(); ++i) {
            if (words[i] == word1) {
                if (index1 != -1) {
                    dist = min(dist, abs(index1 - i));
                }
                index1 = i;
            } else if (words[i] == word2) {
                index2 = i;
            }
            if (index1 != -1 && index2 != -1) {
                dist = min(dist, abs(index1 - index2));
            }
        }
        return dist;
    }
};