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

243 - Shortest Word Distance

Question

Algorithm

Code

All Problems

All Solutions