leetcode-243. 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.

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 that word1 does not equal to word2, and word1 and word2 are both in the list.
原题地址

感觉自己就跟zz一样。

首先扔出自己的2b解法。O(n) time, and O(n) space.

int shortestDistance(vector<string>& words, string word1, string word2) {
    unordered_map<string, vector<int>> hash;
    for (int i = 0; i < words.size(); i++)
        hash[words[i]].push_back(i);
    vector<int> vec1 = hash[word1];
    vector<int> vec2 = hash[word2];
    int diff = INT_MAX, i1 = 0, i2 = 0;
    while (i1 < vec1.size() && i2 < vec2.size()) {
        if (vec1[i1] < vec2[i2]) {
            diff = min(diff, vec2[i2] - vec1[i1]);
            i1++;
        }
        else {
            diff = min(diff, vec1[i1] - vec2[i2]);
            i2++;
        }
    }
    return diff;

然后在网上看到比较标准的解法。

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

然后又看到了更为简洁的写法。

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

精益求精。