面试题 17.11

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. If the operation will be repeated many times for the same file (but different pairs of words), can you optimize your solution?

Example:

Input: words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student" Output: 1 Note:

words.length <= 100000

Solutions

1. two pointers O(n)

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

1. preprocess with hash map

2. Suits for the follow up problem.

class Solution {
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        // preprocess
        unordered_map<string, vector<int>> m;
        for (int i = 0; i < words.size(); i++)
            m[words[i]].push_back(i);

        auto & v1 = m[word1];
        auto & v2 = m[word2];
        if (v1.empty() || v2.empty())
            return -1;

        // two pointers, similar to merge two sorted lists
        int prev_is1 = true, prev = -0x3f3f3f3f;
        int i1 = 0, i2 = 0, res = INT_MAX;
        while (i1 < v1.size() || i2 < v2.size()) {
            int cur, cur_is1;
            if (i1 < v1.size() && (i2 == v2.size() || v1[i1] < v2[i2])) {
                cur = v1[i1++];
                cur_is1 = true;
            }
            else {
                cur = v2[i2++];
                cur_is1 = false;
            }
            if (prev_is1 != cur_is1)
                res = min(res, cur - prev);
            prev = cur;
            prev_is1 = cur_is1;
        }

        return res;
    }
};