245.md

【中规中矩】245. 最短单词距离 III （多解法且多语言实现）

解题思路

此题跟243 最短单词距离 I， 244 最短单词距离 II相似。准确的讲跟I最接近。如果没做过243 最短单词距离 I 建议先做一下那道题。理解243题最后，该题于243唯一的区别就是现在允许word1跟word2相同。之前最短单词距离I中不允许word1和word2相同。其实只需要解法1和解法2的基础上，判断跳过两个index指向同一个单词的情况（否则距离会被计算为0）。解法3，需要加上word1 == word2情况的判断条件。

代码

class Solution1 {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        unordered_map<string, vector<int>> mp;
        for (int i = 0; i < wordsDict.size(); i++) {
            mp[wordsDict[i]].push_back(i);
        }

        int minDist = numeric_limits<int>::max();
        for (const auto& idx1 : mp[word1]) {
            for (const auto& idx2 : mp[word2]) {
                if (idx1 != idx2) {
                    minDist = min(minDist, abs(idx1 - idx2));
                }
            }
        }

        return minDist;
    }
};


class Solution2 {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        int idx1 = -1;
        int idx2 = -1;
        int minDist = numeric_limits<int>::max();
        for (int i = 0; i < wordsDict.size(); i++) {
            if (wordsDict[i] == word1) {
                idx1 = (word1 == word2 ? idx2 : i);
            }
            
            if (wordsDict[i] == word2) {
                idx2 = i;
            }
            
            // idx1 != idx2 条件可选，因为word1 == word2的时候。我们上面已经把idx1设置为了idx2的上一个值
            if (idx1 != -1 && idx2 != -1 && idx1 != idx2) { 
                minDist = min(minDist, abs(idx1 - idx2));
            }
        }

        return minDist;
    }
};

class Solution3 {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        int idx = -1;
        int minDist = numeric_limits<int>::max();
        for (int i = 0; i < wordsDict.size(); i++) {
            if (wordsDict[i] == word1 || wordsDict[i] == word2) {
                if (idx != -1 && (wordsDict[i] != wordsDict[idx] || word1 == word2)) { 
                    minDist = min(minDist, abs(i - idx));
                }
                idx = i;
            }
        }

        return minDist;
    }
};

class Solution1(object):
    def shortestWordDistance(self, words, word1, word2):
        mp = dict()
        for i, word in enumerate(words):
            if word not in mp:
                mp[word] = [i]
            else:
                mp[word].append(i)

        minDist = float('inf')
        for idx1 in mp[word1]:
            for idx2 in mp[word2]:
                if (idx1 != idx2):
                    minDist = min(minDist, abs(idx1 - idx2))

        return minDist

class Solution2(object):
    def shortestWordDistance(self, words, word1, word2):
        idx1 = -1
        idx2 = -1
        minDist = float('inf')
        for i, word in enumerate(words):
            if word == word1:
                idx1 = (idx2 if word1 == word2 else i)
            if word == word2:
                idx2 = i
            if (idx1 != -1 and idx2 != -1 and idx1 != idx2):
                minDist = min(minDist, abs(idx1 - idx2))

        return minDist

class Solution {
    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        int idx = -1;
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < wordsDict.length; i++) {
            if (wordsDict[i].equals(word1) || wordsDict[i].equals(word2)) {
                if (idx != -1 && (!wordsDict[i].equals(wordsDict[idx]) || word1.equals(word2))) { 
                    minDist = Math.min(minDist, Math.abs(i - idx));
                }
                idx = i;
            }
        }

        return minDist;        
    }
}

点我赞赏作者

github 题解