244. Shortest Word Distance II - cocoder39/coco39_LC GitHub Wiki

244. Shortest Word Distance II

time complexity is O(v1.size() + v2.size()) = O(n)

while (i < v1.size() && j < v2.size()) {
            res = min(res, abs(v1[i] - v2[j]));
            v1[i] > v2[j] ? j++ : i++;
        }

which is much better than my initial idea

for() {
    for () {
    }
}

where the complexity is (O(v1.size() * v2.size()), worst case is O(n/2 * n/2) = O(n ^ 2)

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

    int shortest(string word1, string word2) {
        int res = INT_MAX;
        vector<int>& v1 = map[word1];
        vector<int>& v2 = map[word2];
        
        int i = 0, j = 0;
        while (i < v1.size() && j < v2.size()) {
            res = min(res, abs(v1[i] - v2[j]));
            v1[i] > v2[j] ? j++ : i++;
        }
        return res;
    }
private:
    unordered_map<string, vector<int>> map;
};
⚠️ **GitHub.com Fallback** ⚠️