# Word Distance

Design a class which receives a list of words in the constructor, and implements a method that takes two words \_word1 \_and \_word2 \_and return the shortest distance between these two words in the list.

## **Example**

Assume that words =`["practice", "makes", "perfect", "coding", "makes"]`.

```
Input:
word1 = “coding”, 
word2 = “practice”
Output: 3
```

```
Input:
word1 = "makes", 
word2 = "coding"
Output: 1
```

## Note 1

**只call一次的normal情况**

遍历一遍words list，找到word1就更新pointer1，找到word2就更新pointer2。\
每找到任何一个word，就计算出当前distance，跟min打擂台。

时间复杂度：O(n)\
空间复杂度：O(1)

## Code1

```java
public int shortestDistance1(String[] words, String word1, String word2) {
    int one = -1, two = -1;
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < words.length; i++) {
        if (word1.equals(words[i])) {
            one = i;
        }
        if (word2.equals(words[i])) {
            two = i;
        }

        if (one != -1 && two != -1) {
            res = Math.min(res, Math.abs(one - two));
        }
    }

    return res;
}
```

## Note 2

**多次调用**

会调用shortest函数非常多次，所以使用HashMap来存储words，key为word，value为index组成的list。\
计算shortest word distance的时候，使用双指针遍历一遍即可。

时间复杂度\
存储：O(N)，查找：O(m+n)/O(N)

空间复杂度\
存储：O(N)，查找：O(N)

## Code 2

```java
HashMap<String, List<Integer>> map;

    public WordDistance(String[] words) {
        map = new HashMap();
        for (int i = 0; i < words.length; i++) {
            List<Integer> indexes = map.getOrDefault(words[i], new ArrayList());
            indexes.add(i);
            map.put(words[i], indexes);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> p1 = map.get(word1);
        List<Integer> p2 = map.get(word2);
        int min = Integer.MAX_VALUE;
        int i = 0, j = 0;
        while (i < p1.size() && j < p2.size()) {
            int wp1 = p1.get(i);
            int wp2 = p2.get(j);
            if (wp1 < wp2) {
                min = Math.min(min, wp2 - wp1);
                i++;
            } else {
                min = Math.min(min, wp1 - wp2);
                j++;
            }
        }
        return min;
    }
```

## Note 3

**相同单词不同位置**

标示一下是否是相同的单词，不是相同的就正常处理，相同就单独处理一下

当遍历单词与单词1相同时，如果是same的话，two就更新为one

```java
if (same) {
    two = one; //former one
}
```

## Code 3

```java
public int shortestWordDistance(String[] words, String word1, String word2) {
    boolean same = word1.equals(word2);
    int one = -1, two = -1;
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < words.length; i++) {
        if (words[i].equals(word1)) {
            if (same) {
                two = one; //former one
            }
            one = i;
        } else if (words[i].equals(word2)) {
            two = i;
        }
        if (one != -1 && two != -1) {
            res = Math.min(res, Math.abs(one - two));
        }
    }

    return res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luj.gitbook.io/code/tricky/word-distance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.