243. Shortest Word Distance

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

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

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

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

S: 记录最新的word1，word2坐标，持续更新shortest distance即可

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

244. Shortest Word Distance II

This is afollow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and 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 thatword1does not equal toword2, andword1andword2are both in the list.

S: hash map

因为要call多次，考虑用hash map存储每个word的坐标序列以便快速检索.

注意每个word可能出现多次，最后会得到有序的index序列

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

    int shortest(string word1, string word2) {
        if (word1 == word2) return 0;
        vector<int> idx1 = dict[word1];
        vector<int> idx2 = dict[word2];
        int minDist = INT_MAX;
        int i = 0, j = 0;
        while (i < idx1.size() && j < idx2.size()) {
            minDist = min(minDist, abs(idx1[i] - idx2[j]));
            if (idx1[i] > idx2[j]) {
                j++;
            } else {
                i++;
            }
        }
        return minDist;
    }
private:
    unordered_map<string, vector<int>> dict;
};

245. Shortest Word Distance III

This is afollow upofShortest Word Distance. The only difference is nowword1could be the same asword2.

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

word1andword2may be the same and they represent two individual words in the list.

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

Givenword1=“makes”,word2=“coding”, return 1.
Givenword1="makes",word2="makes", return 3.

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

S: 在原解基础上排除同一位置的情况

    int shortestWordDistance(vector<string>& words, string word1, string word2) {
        int idx1 = -1, idx2 = -1, minDist = INT_MAX;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1) {
                idx1 = i;
                if (idx2 != -1 && idx1 != idx2) {
                    minDist = min(minDist, abs(idx1 - idx2));
                }
            }
            if (words[i] == word2) {
                idx2 = i;
                if (idx1 != -1 && idx1 != idx2) {
                    minDist = min(minDist, abs(idx1 - idx2));
                }
            }
        }
        return minDist;        
    }