243

243. Shortest Word Distance (Easy)

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.

Companies:
LinkedIn, Amazon

Related Topics:
Array

Similar Questions:

• Shortest Word Distance II (Medium)
• Shortest Word Distance III (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/shortest-word-distance/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int prev1 = -1, prev2 = -1, ans = INT_MAX;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1) {
                if (prev2 != -1) ans = min(ans, i - prev2);
                prev1 = i;
            }
            if (words[i] == word2) {
                if (prev1 != -1) ans = min(ans, i - prev1);
                prev2 = i;
            }
        }
        return ans;
    }
};