leetcode:单词距离

两层循环

两层循环，作为一种最直观的算法，是最容易想到的。两层循环能解决多种问题，比如排序中的选择排序、插入排序、交换排序，均是通过两层循环的方式来实现。这种算法的缺点是时间复杂度高，为O(n2)。

class Solution {
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        int size = words.size();
        int ret = size;
        for (int i = 0; i < size; i++) {
            if (words[i] == word1) {
                for (int j = 0; j < size; j++) {
                    if (words[j] == word2) {
                        if (j < i) {
                            ret = (i - j < ret)? (i - j) : ret;
                        } else {
                            ret = (j - i < ret)? (j - i) : ret;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

一层循环(动态规划)

维护两个下标index1和index2，均初始化为-1。遍历数组，当遍历到word1时更新index1，遍历到word2时更新index2。当index1和index2均不为-1时，则计算两者之差，如果两者之差比上一次计算的值小，则进行更新，否则不更新。数组遍历结束之后，就得到了想要的结果。

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

扩展

题干中说，如果文件多次输入，并且每次的两个单词都不相同，能不能优化？

对于这种情况，上边的两种方式，都可以解决，缺点是时间复杂度偏高。并且每次都要遍历一遍单词，工作重复。想要避免这种重复的工作，可以在第一次遍历的时候将每个单词的下标用map保存下来，map的key是word，value是单词下标的vector，单词下标从小到大进行存放。

class Solution {
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        if (scanOnce_) {
            return getResult(word1, word2);
        } else {
            int size = words.size();
            for (int i = 0; i < size; i++) {
                wordIndex_[words[i]].push_back(i);
            }
            return getResult(word1, word2);
        }
    }

    int getResult(string word1, string word2) {
        int ret = 100000;
        for (int index1 : wordIndex_[word1]) {
            for (int index2 : wordIndex_[word2]) {
                if (index1 > index2) {
                    ret = (index1 - index2 < ret) ? (index1 - index2) : ret;
                } else {
                    ret = (index2 - index1 < ret) ? (index2 - index1) : ret;
                }
            }
        }
        return ret;
    }

private:
    std::map<string, std::vector<int>> wordIndex_;
    bool scanOnce_ = false;
};