【MEDIUM】Shortest Word Distance II

发布于: 2019-03-02 17:15
阅读: 40
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/shortest-word-distance-ii/

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. Your method will be called repeatedly many times with different parameters.

Example:

Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:

  • You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

分析过程

  • 输入:一个单词数组以及两个单词,这两个单词假定一定包含在数组内。
  • 输出:这两个单词的最短距离。
  • 思路:由于这个方法需要多次调用,每次调用都遍历一遍就非常不经济了。
    • 考虑使用哈希表把每个单词的索引都存起来,每次求距离时直接在哈希表里寻找。
    • 在哈希表里寻找时不要暴力查找,可以使用游标来计算最接近的几种情况,见注释。

解决方法

class WordDistance {
    
    var hashedList = [String: [Int]]()
    
    init(_ words: [String]) {
        for (i, word) in words.enumerated() {
            if hashedList[word] == nil {
                hashedList[word] = [i]
            } else {
                hashedList[word]!.append(i)
            }
        }
    }
    
    func shortest(_ word1: String, _ word2: String) -> Int {
        guard let word1Indexs = hashedList[word1], let word2Indexs = hashedList[word2] else {
            return -1
        }
        var result = Int.max
        var i = 0
        var j = 0
        // 两个游标从0开始向后遍历,两者小的那个往后移动
        // 这样能保证根据两个游标取的值接近,结果肯定在这些情况里面
        while i < word1Indexs.count && j < word2Indexs.count {
            result = min(result, abs(word1Indexs[i] - word2Indexs[j]))
            if word1Indexs[i] < word2Indexs[j] {
                i += 1
            } else {
                j += 1
            }
        }
        
        return result
    }
}

Thanks for reading.

All the best wishes for you! 💕