Java: only need to keep one index


  • 43
    B
    public int shortestDistance(String[] words, String word1, String word2) {
       int index = -1, minDistance = Integer.MAX_VALUE;
       for (int i = 0; i < words.length; i++) {
          if (words[i].equals(word1) || words[i].equals(word2)) {
             if (index != -1 && !words[index].equals(words[i])) {
                minDistance = Math.min(minDistance, i - index);
              }
              index = i;
          }
       }
       return minDistance;
    }

  • 2
    P

    My C++ version with the same idea. Here is a brief explanation: By ignoring irrelevant words, the shortest distance only occurs when word1 and word2 rotate, as below:
    A A A B B B B A A A
    To be clear, two variables prevIndex and prevWord are used.

    int shortestDistance(vector<string>& words, string word1, string word2) {
        int res = INT_MAX, prevIndex = -1;
        string prevWord = "";
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == word1 || words[i] == word2) {
                if (prevWord != "" && words[i] != prevWord) { //when word1 and word2 rotate
                    res = min(res, i - prevIndex);
                }
                prevIndex = i;
                prevWord = words[i];
            }
        }
        return res;
    }

  • 0

    same idea, but more elegant than mine.


  • 1
    M

    Code with single index surely looks neat but may not be great for runtime. String comparison is expensive task. Consider an array of strings that is filled with large size words and filled with a lot of word2.
    With two index, at max we will compare each word2 twice where as in this we will compare it three times. Better to pay price of arithmetic operation compared to string equals.

    Also we can break out of the loop if you ever see distance 1, we are never going to find better distance than that.


Log in to reply
 

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