Short and easy to understand Java AC O(n)


  • 0

    Update positions of word1 index1, positions word2 index2 every time we encounter them,
    and update the distance between lastest postions.
    In case word1 == word2, index1 and index2 get both updated for one occurance of word.

    public class Solution {
        public int shortestWordDistance(String[] words, String word1, String word2) {
            int min = Integer.MAX_VALUE;
            int index1 = -1; // last seen position of word1
            int index2 = -1; // last seen position of word2
            for (int i = 0; i < words.length; i++) {
                if (words[i].equals(word1)) {
                    index1 = i;
                    if (index2 != -1)
                        min = Math.min(min, index1 - index2);
                } // no "else" here to allow index2 to be updated to the same value as index1 in case word1==word2.
                if (words[i].equals(word2)) {
                    index2 = i;
                    if (index1 != -1 && index1 != index2) // index1 != index2 to avoid 0 distance bug in case word1 == word2.
                        min = Math.min(min, index2 - index1);
                }
            }
            return min;
        }
    }

  • 0

    index1 = -1 means word1 has not appeared yet so don't update min yet.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.