Given an array of words and two target words, the task is to find the shortest distance (minimum number of words) between the two target words in the array. The distance is calculated by counting the number of words between the two target words, excluding the target words themselves.
Approaches to find the shortest distance between two words
Table of Content
Approach 1: Brute Force
One straightforward approach is to iterate through the array and keep track of the indices of the two target words. Then, compute the minimum distance between the indices.
Example: This example shows the use of the above-explained approach.
Javascript
function shortestDistance(words, word1, word2) { let minDistance = Number.MAX_SAFE_INTEGER; let index1 = -1; let index2 = -1; let i = 0; while (i < words.length) { if (words[i] === word1) { index1 = i; minDistance = index2 !== -1 ? Math.min( minDistance, Math.abs(index1 - index2) ) : minDistance; } else if (words[i] === word2) { index2 = i; minDistance = index1 !== -1 ? Math.min( minDistance, Math.abs(index1 - index2) ) : minDistance; } i++; } return minDistance; } const wordsArray = ["apple", "banana", "orange", "apple", "kiwi", "cherry" ]; const word1 = "apple"; const word2 = "banana"; console.log(shortestDistance(wordsArray, word1, word2)); |
1
Approach 2: Optimal Approach
Another efficient approach is to keep track of the last indices where each word appeared while traversing the array. Then, calculate the distance and update the minimum distance whenever one of the words is found.
Example: This example shows the use of the above-explained approach.
Javascript
function shortestDistance(words, word1, word2) { let minDistance = Number.MAX_SAFE_INTEGER; let index1 = -1; let index2 = -1; let i = 0; while (i < words.length) { if (words[i] === word1) { index1 = i; } else if (words[i] === word2) { index2 = i; } if (index1 !== -1 && index2 !== -1) { minDistance = Math.min( minDistance, Math.abs(index1 - index2) ); } i++; } return minDistance; } // Example usage: const wordsArray = [ "apple", "banana", "orange", "apple", "kiwi", "banana" ]; const word1 = "apple"; const word2 = "banana"; console.log(shortestDistance(wordsArray, word1, word2)); |
1