Shortest Word Distance I,II, III

桃扇骨 2021-12-17 10:43 223阅读 0赞

这是一系列linkedin的面试题，比较接近于Indeed的面试题目，follow up加ＯＯ的多接口形式．

Shortest Word Distance

Given a list of words and two words *word1* and *word2*, return the shortest distance between these two words in the list.

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

Given *word1* = `“coding”`, *word2* = `“practice”`, return 3.  
Given *word1* = `"makes"`, *word2* = `"coding"`, return 1.

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

这个是简单的扫描问题，two pointer解决，p1,p2分别记录word1和word2在wordlist当中的位置．一旦p1,p2有更新,则计算一次距离，和当前最小距离比较．这样，每次都是超前找最相近的另一个单词．可以找到word1附近离他最近的word2（有前右后）,　word2附近离他最近的word1(有前右后）．总之可以保证找到最小距离．

时间复杂度Ｏ(n),空间复杂度Ｏ(1)

代码如下：

class Solution {
    public:
        int shortestDistance(vector<string>& words, string word1, string word2) {
            int p1 = -1;
            int p2 = -1;
            int dis = words.size();
            for(int i=0; i < words.size(); i++){
                if (words[i] == word1)
                    p1 = i;
                if (words[i] == word2)
                    p2 = i;
                if (p1!=-1 && p2 != -1)
                    dis = min(dis, abs(p1-p2));
            }
            return dis;
        }
    };

### Shortest Word Distance II ###

This is a **follow up** of [Shortest Word Distance][]. The only difference is now you are given the list of words and your method will be called *repeatedly* many times with different parameters. How would you optimize it?

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.

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

Given *word1* = `“coding”`, *word2* = `“practice”`, return 3.  
Given *word1* = `"makes"`, *word2* = `"coding"`, return 1.

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

Ｉ的follow　up, 和Indeed的find k nearest stars 类似，注意到这里需要多次调用该方法，且参数不同．所以需要优化，不能每次都Ｏ(n)扫一遍，解决策略是　先建一个hashmap，把每个单词出现的index list先缓存起来，这样每次就是在word1的index list和word2的index list当中找距离最近的数字．其实就是[The Smallest Difference．][The Smallest Difference]而且因为hashmap按序添加，这里的两个list都是有序的．不需要预先排序.所以双指针一遍扫描，复杂度为两个list的长度相加Ｏ(n1+n2).代码如下：　核心思路为舍去不可能的方向．

class WordDistance(object):
        def __init__(self, words):
            """
            initialize your data structure here.
            :type words: List[str]
            """
            self.hash = {}
            for i in xrange(len(words)):
                if words[i] not in self.hash:
                    self.hash[words[i]] = [i]
                else:
                    self.hash[words[i]].append(i)
    
        def shortest(self, word1, word2):
            """
            Adds a word into the data structure.
            :type word1: str
            :type word2: str
            :rtype: int
            """
            #two pointer,min difference
            res = sys.maxint
            p1 = 0
            p2 = 0
            list1 = self.hash[word1]
            list2 = self.hash[word2]
            while p1 < len(list1) and p2 < len(list2):
                if list1[p1] >= list2[p2]:　　　　
                    res = min(res, (list1[p1]-list2[p2]))
                    p2 += 1　＃此时增加P1,不会有更好的结果
                else:
                    res = min(res, (list2[p2] - list1[p1]))
                    p1 += 1　＃此时增加p2,b不会有更好的结果
                   
            return res

### Shortest Word Distance III ###

This is a **follow up** of [Shortest Word Distance][]. The only difference is now *word1* could be the same as *word2*.

Given a list of words and two words *word1* and *word2*, return the shortest distance between these two words in the list.

*word1* and *word2* may be the same and they represent two individual words in the list.

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

Given *word1* = `“makes”`, *word2* = `“coding”`, return 1.  
Given *word1* = `"makes"`, *word2* = `"makes"`, return 3.

**Note:**  
You may assume *word1* and *word2* are both in the list.

主要是处理重复情况，思路是Ｉ的基础上加一个flag标志．代码如下：

class Solution(object):
        def shortestWordDistance(self, words, word1, word2):
            """
            :type words: List[str]
            :type word1: str
            :type word2: str
            :rtype: int
            """
            #word1 and word2 are the same words, how to handle the same situation into the one situation.
            res = sys.maxint
            if word1 == word2:
                flag = True else:
               flag = False
            p1 = -1
            p2 = -1
            for i in xrange(len(words)):
                if words[i] == word1:
                    if flag and p1!= -1:
                        res = min(res, i-p1)
                    elif not flag and p2 != -1:
                        res = min(res, i-p2)
                    p1 = i
                if words[i] == word2:
                    if not flag and p1 != -1:
                        res = min(res, i-p1)
                    p2 = i
            return res

转载于:https://www.cnblogs.com/sherylwang/p/5833379.html

[Shortest Word Distance]: https://leetcode.com/problems/shortest-word-distance
[The Smallest Difference]: http://www.lintcode.com/en/problem/the-smallest-difference/