Question

Formatted question description: https://leetcode.ca/all/243.html

 243	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.

 @tag-array

Algorithm

It is enough to traverse the array once, initialize the two variables p1, p2 to -1, and then traverse the array.

When word 1 is encountered, its position is stored in p1, and if word 2 is encountered, its position is stored in p2. If p1, p2 are not -1 anymore, then update the result.

Code

Java

  • 
    public class Shortest_Word_Distance {
    
        public static void main(String[] args) {
            Shortest_Word_Distance out = new Shortest_Word_Distance();
            Solution s = out.new Solution();
    
            System.out.println(s.shortestDistance(new String[]{"practice", "makes", "perfect", "coding", "makes"}, "makes", "coding"));
        }
    
        public class Solution {
            public int shortestDistance(String[] words, String word1, String word2) {
                int posA = -1;
                int posB = -1;
                int minDistance = Integer.MAX_VALUE;
    
                for (int i = 0; i < words.length; i++) {
                    if (words[i].equals(word1)) {
                        posA = i;
                    }
    
                    if (words[i].equals(word2)) {
                        posB = i;
                    }
    
                    if (posA != -1 && posB != -1) { // will be run every time, after 1st pair is found
                        minDistance = Math.min(minDistance, Math.abs(posA - posB));
                    }
                }
    
                return minDistance;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/shortest-word-distance/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int shortestDistance(vector<string>& words, string word1, string word2) {
            int prev1 = -1, prev2 = -1, ans = INT_MAX;
            for (int i = 0; i < words.size(); ++i) {
                if (words[i] == word1) {
                    if (prev2 != -1) ans = min(ans, i - prev2);
                    prev1 = i;
                }
                if (words[i] == word2) {
                    if (prev1 != -1) ans = min(ans, i - prev1);
                    prev2 = i;
                }
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        idx1 = idx2 = -1
        ans = len(words)
        for i in range(0, len(words)):
          word = words[i]
          if word in (word1, word2):
            if word == word1:
              idx1 = i
            elif word == word2:
              idx2 = i
            if idx1 != -1 and idx2 != -1:
              ans = min(ans, abs(idx2 - idx1))
        return ans
    
    

All Problems

All Solutions