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;
        }
    }
}

All Problems

All Solutions