This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given a list of words and two words *word1* and *word2*, return the shortest distance between these two words in the list.

For example,

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

.

Given *word1* = `“coding”`

, *word2* = `“practice”`

, return 3.

Given *word1* = `"makes"`

, *word2* = `"coding"`

, return 1.

**Note:**

You may assume that *word1* **does not equal to** *word2*, and *word1* and *word2* are both in the list.

b'

\n\n## Solution

\n

\n#### Approach #1 (Brute Force) [Accepted]

\n\n

\n#### Approach #2 (One-pass) [Accepted]

\n\n

'
This is a straight-forward coding problem. The distance between any two positions and in an array is . To find the shortest distance between `word1`

and `word2`

, we need to traverse the input array and find all occurrences and of the two words, and check if is less than the minimum distance computed so far.

\n

**Algorithm**

A naive solution to this problem is to go through the entire array looking for the first word. Every time we find an occurrence of the first word, we search the entire array for the closest occurrence of the second word.

\n**Java**

public int shortestDistance(String[] words, String word1, String word2) {\n int minDistance = words.length;\n for (int i = 0; i < words.length; i++) {\n if (words[i].equals(word1)) {\n for (int j = 0; j < words.length; j++) {\n if (words[j].equals(word2)) {\n minDistance = Math.min(minDistance, Math.abs(i - j));\n }\n }\n }\n }\n return minDistance;\n}\n

**Complexity Analysis**

The time complexity is , since for every occurrence of `word1`

, we traverse the entire array in search for the closest occurrence of `word2`

.

Space complexity is , since no additional space is used.

\n\n

**Algorithm**

We can greatly improve on the brute-force approach by keeping two indices `i1`

and `i2`

where we store the *most recent* locations of `word1`

and `word2`

. Each time we find a new occurrence of one of the words, we do not need to search the entire array for the other word, since we already have the index of its most recent occurrence.

**Java**

public int shortestDistance(String[] words, String word1, String word2) {\n int i1 = -1, i2 = -1;\n int minDistance = words.length;\n int currentDistance;\n for (int i = 0; i < words.length; i++) {\n if (words[i].equals(word1)) {\n i1 = i;\n } else if (words[i].equals(word2)) {\n i2 = i;\n }\n\n if (i1 != -1 && i2 != -1) {\n minDistance = Math.min(minDistance, Math.abs(i1 - i2));\n }\n }\n return minDistance;\n}\n

**Complexity Analysis**

The time complexity is . This problem is inherently linear; we cannot do better than because at the very least, we have to read the entire input.

\nSpace complexity is , since no additional space is allocated.

\nAnalysis written by: @noran

\n