# Shortest Word Distance 类

## [Shortest Word Distance](https://leetcode.com/problems/shortest-word-distance/)

### 数组内单词可能有重复，所以需要在 word1 & word2 的多次出现位置中，寻找最近的。

### 用一些数组的小 trick，比如 index = -1 作为 “还没找到” 的初始化条件，而两个指针所保存的，都是 word1 / word2 所最近出现的位置，one-pass 即可。

```java
public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int minDis = Integer.MAX_VALUE;
        int oneIndex = -1, twoIndex = -1;

        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)) oneIndex = i;
            if(words[i].equals(word2)) twoIndex = i;

            if(oneIndex != -1 && twoIndex != -1) 
                minDis = Math.min(minDis, Math.abs(oneIndex - twoIndex));
        }
        return minDis;
    }
}
```

## [Shortest Word Distance II](https://leetcode.com/problems/shortest-word-distance-ii/)

### 这样的问题设计方式实在提醒自己问清楚问题要求，比如 wordList 大小，是否有重复，函数调用次数是否频繁等等。这题在原先基础上增加了 data structure API 调用的考量。

### 思路很简单，调用多次之后每次再去重新扫很不经济，需要数据结构去存储每个 word 出现的位置，每次 API 调用时直接在两个 list 中找最小距离。

### 比较两个 list 的方法类似窗口型双指针的基本思想：虽然双指针所能组成的 pair 数量是 n^2，但是对于指定位置的 ptr，我们可以证明后面的所有 pair 组合都是没有意义的，因此可以把指针单向移动。

```java
public class WordDistance {
    HashMap<String, List<Integer>> map;
    public WordDistance(String[] words) {
        map = new HashMap<String, List<Integer>>();

        for(int i = 0; i < words.length; i++){
            String str = words[i];
            if(map.containsKey(str)){
                map.get(str).add(i);
            } else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(str, list);
            }
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> oneList = map.get(word1);
        List<Integer> twoList = map.get(word2);

        int ptr1 = 0, ptr2 = 0;
        int minDis = Integer.MAX_VALUE;

        while(ptr1 < oneList.size() && ptr2 < twoList.size()){
            minDis = Math.min(minDis, Math.abs(oneList.get(ptr1) - twoList.get(ptr2)));
            if(oneList.get(ptr1) < twoList.get(ptr2)){
                ptr1 ++;
            } else {
                ptr2 ++;
            }
        }

        return minDis;
    }
}
```

## [Shortest Word Distance III](https://leetcode.com/problems/shortest-word-distance-iii/)

改成 word1 有可能等于 word2 之后，这题的重点就变成了各种 corner case 怎么处理，比如

【"a","c","a","a"】, word1 = "a", word2 = "a"

【"a", "a"】, word1 = "a", word2 = "a"

换句话讲，就是看你能否考虑到各种情况正确地 assign index.

```java
public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int ptr1 = -1, ptr2 = -1;
        boolean isSame = word1.equals(word2);
        int minDis = Integer.MAX_VALUE;

        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)){
                if(isSame){
                    ptr1 = ptr2;
                    ptr2 = i;
                } else {
                    ptr1 = i;
                }
            } else if(words[i].equals(word2)){
                ptr2 = i;
            }

            if(ptr1 != -1 && ptr2 != -1) minDis = Math.min(minDis, Math.abs(ptr1 - ptr2));
        }

        return minDis;
    }
}
```


---

# 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://mnunknown.gitbook.io/algorithm-notes/linkedin_mian_jing/shortest_word_distance_lei.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.