243_Shortest Word Distance

243. Shortest Word Distance

Level: easy

Tag: array

Question

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.

Example1

Input: words = ["practice", "makes", "perfect", "coding", "makes"]
       word1 = “coding”
       word2 = “practice”
Output: 3

Idea 1 (brute force)

Find all the positions $p_1,p_2$ for word1 and word2, and compute the shortest distance by minimizing $|p_1 - p_2|$.

Complexity 1

• Time:$O(n+k^2)$ where $n$ is the length of the array and $k$ is the maximum number of word1 and word2.
• Space:$O(k)$

Solution 1

class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """

        p1, p2 = [], []

        # find position for word1 and word2
        for i in range(len(words)):
            if words[i] == word1:
                p1.append(i)
            elif words[i] == word2:
                p2.append(i)

        # find shortest distance
        distance = len(words)
        for i in p1:
            for j in p2:
                distance = min(distance, abs(i-j))

        return distance

Idea 2 (greedy)

Keep two indices $p_1,p_2$ where we store the most recent locations of word1 and word2. Update shortest distance when we scan from left to right.

Complexity 2

• Time:$O(n)$ where $n$ is the length of the array
• Space:$O(1)$

Solution 2

class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """

        n = len(words)
        distance = n
        p1 = p2 = -n
        for i in range(n):
            if words[i] == word1:
               p1 = i
               distance = min(distance, i - p2)
            elif words[i] == word2:
               p2 = i
               distance = min(distance, i - p1)
        return distance