> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/hashtable/244.-shortest-word-distance-ii.md).

# 244. Shortest Word Distance II

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MamEtNlctU9ed4bvqcZ%2F-MaqIetOkaNGzAkx_NsO%2Fimage.png?alt=media\&token=39fb3227-652e-438f-ae3d-71054d366703)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MamEtNlctU9ed4bvqcZ%2F-MaqIkKtJVjRCqU7mtax%2Fimage.png?alt=media\&token=6212af0a-8746-474e-9590-c7106ace6aa5)

###

244 is for huge data size, 243 is for small data size

###

### Solution1: 

### compare two lists, one by one => time: O(n^2)

### Solution2: 

use two pointer => O(n + m)

because the map\<String, List\<Integer>>, the list adds by order and not repeated,

the shortest distance happened at two list's closest index&#x20;

ex:

&#x20; i

&#x20;               j

\[ 1(a3), 2(a4), 3(a4), 6(a3), 8(a4) ]

when a\[i] < a\[j]   we should i++ .=>  to find next min . **(not move j, that's will increase the distance , right?)**

&#x20;                                      i

&#x20;               j

\[ 1(a3), 2(a4), 3(a4), 6(a3), 8(a4) ]

until ending

time: O(n), n is the wordsDict's length

space: O(n)

```java
class WordDistance {

    private Map<String, List<Integer>> map = new HashMap<>();
    public WordDistance(String[] wordsDict) {
        for (int i = 0; i < wordsDict.length ; i++) {
            String w = wordsDict[i];
            List<Integer> data = map.getOrDefault(w, new ArrayList<>());
            data.add(i);
            map.put(w, data);
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> data1 = map.get(word1);
        List<Integer> data2 = map.get(word2);
        
        int i = 0, j = 0;
        int min = Integer.MAX_VALUE;
        while (i < data1.size() && j < data2.size()) {
            min = Math.min(min, Math.abs(data1.get(i) - data2.get(j)));
            
            if (data1.get(i) > data2.get(j)) {
                j++;
            } else {
                i++;
            }
        }
        return min;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.shortest(word1,word2);
 */
```

## Solution 3:

in two lists, for loop and  use binary search

time: O(m \* logn)

space: O(n)