LeetCode 243~245 Shortest Word Distance I, II, & III

LeetCode Record

LeetCode

Question 1: 243 Shortest Word Distance I

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

Note：

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

Example:

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

Input:word1 = 「coding」, word2 = 「practice」Output:3

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

Thought 1 — Hash table by my intuition

此方法需要traversal整個array來建立hash table, 之後再去比較其value中的最小距離

Thought 2 — Two array

給予兩個array, 內容為兩個input值出現在words中的index值, 需要traversal整個array來建立此兩個array, 之後再去比較其value中的最小距離, Time complxity與 Thought1 差不多

Thought 3 — Two points

設index1, index2 = -1, -1 , traversal整個array 若word1出現且index2為-1則word1紀錄index1=i; 若word2出現且index1為-1則記錄index2=i; 若index1 != -1 且 index2 != -1 則找最短距離與目前最優解做比較 取最小值

def getShortest(self, word1, word2):
        i1 , i2 = -1, -1
        shortest = float('inf')
        for i in range(len(self.words)):
            if self.words[i] == word1:
                i1 = i
            if self.words[i] == word2:
                i2 = i
            if i1 != -1 and i2 != -1:
                shortest = min(shortest, abs(i1-i2))
        return shortest

Question 2: 244 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.

Thought 1 — Hash table

此題要求完成一個function能夠多次被call, 因此需要做optimize, 所以hash table能夠派上用場, 因為其Query的時間複雜度為O(1), 接下來使用two point去比較兩個list的值, 找出最短距離, 注意index增加的判斷條件!

因為此題在LeetCode上是Locked, 我自己嘗試著寫出其架構…

from collections import defaultdict
class ShortestWordDistance:
    def __init__(self):
        self.words = ["practice", "makes", "perfect", "coding", "makes"]
        self._map = defaultdict(list)
        self.buildMap()
    
    def buildMap(self):
        for i, w in enumerate(self.words):
            self._map[w].append(i)
    
    def getShortest(self, word1, word2):
        li1 = self._map[word1]
        li2 = self._map[word2]
        index1, index2 = 0, 0
        shortest = float('inf')
        while index1 < len(li1) and index2 < len(li2):
            shortest = min(shortest, abs(li1[index1]-li2[index2]))
            if li1[index1] > li2[index2]:
                index2 += 1
            else:
                index1 += 1
        return shortest
        
s = ShortestWordDistance()
print(s.getShortest("coding", "practice"))
print(s.getShortest("makes", "coding"))

Question 3: 245 Shortest Word Distance III

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.

Example:
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Input: word1 = “makes”, word2 = “coding”
Output: 1
Input: word1 = “makes”, word2 = “makes”
Output: 3
Note:
You may assume word1 and word2 are both in the list.

Thought 1 — Using the answer from Q1 (Intuition)

此題容許input有相同word, 在Q1解裡面增加flag, 以避免word相同的狀況

    # Q3    
    def getShortest(self, word1, word2):
        i1 , i2 = -1, -1
        shortest = float('inf')
        for i in range(len(self.words)):
            pre = i1
            if self.words[i] == word1:
                i1 = i
            if self.words[i] == word2:
                i2 = i
            if i1 != -1 and i2 != -1:
                if word1 == word2 and pre != -1 and pre != i1:
                    shortest = min(shortest, abs(pre-i2))
                elif i1 != i2:
                    shortest = min(shortest, abs(i1-i2))
        return shortest