Shortest Word Distance

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

Example:

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

Input: word1 = "coding", word2 = "practice"
Output: 3

Input: word1 = "makes", word2 = "coding"
Output: 1

Note:

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

---

Solution

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

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