# Facebook高頻題 | Shortest Word Distance的多個變種和解法

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

Note：

You may assume that word1 does not equal to word2, and word1 and word2 are both 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

FLGU一線公司資深工程師

​掃描下方二維碼

Solution 1: Naive Solution

0  1  2  3  4  5  6  7

[a, c, d,b, b, b, c,a]

Input：

word1 = “a”

word2 = “b”

la: 0, 7

lb: 3, 4, 5

Optimize 1: Binary Search

Optimize 2: Two Pointer

if la(i) is smaller, lb(j) is the smallest larger element in lb comparing to la(i)

if lb(j) is smaller, la(i) is the smallest larger element in la comparing to lb(j)

Solution 2

For each a, we need to get the most recent position of b.

For each b, we need to get the most recent position of a.

IndexA：最近一次出現a的位置

IndexB：最近一次出現b的位置

Result：當前的最短距離

Multiple query with unlimited times

Find the Shortest Word Distance

Among k Words