245_Shortest Word Distance III

245. Shortest Word Distance III

Level: medium

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.
word1 and word2 may be the same and they represent two individual words in the list.

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

Example1

Input: words = ["practice", "makes", "perfect", "coding", "makes"]
       word1 = “makes”
       word2 = “makes”
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|$ but only consider the cases that

$$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)
            if words[i] == word2:   # use if instead of elif
                p2.append(i)

        # find shortest distance
        distance = len(words)
        for i in p1:
            for j in p2:
                if i != j:          # don't update when i = j
                    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.

If word1 is not the same as word2, update shortest distance for each new location when we scan from left to right.

If word1 is the same as word2, only update the shortest distance for new location of word1.

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)
            if words[i] == word2:                      # use if instead of elif
               p2 = i
               if word1 != word2:                      # new line
                   distance = min(distance, i - p1)    # new line
        return distance