Shortest Word Distance

🏠 ⬅️ ➡️

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Example 1:

Input: wordsDict = [ "practice ", "makes ", "perfect ", "coding ", "makes "], word1 = "coding ", word2 = "practice " Output: 3

Example 2:

Input: wordsDict = [ "practice ", "makes ", "perfect ", "coding ", "makes "], word1 = "makes ", word2 = "coding " Output: 1

Constraints:

  • 2 <= wordsDict.length <= 3 * 104
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.
  • word1 != word2
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    character(len=10), dimension(n) :: wordsDict = ["practice ", "makes ", "perfect ", "coding ", "makes "]
    character(len=10), intent(in) :: word1, word2
    integer :: dist

    call solve(wordsDict, word1, word2, dist)
    print '(I0)', dist

contains

    subroutine solve(wordsDict, word1, word2, dist)
        implicit none
        character(len=10), dimension(:), intent(in) :: wordsDict
        character(len=10), intent(in) :: word1, word2
        integer, intent(out) :: dist
        integer :: i, j, k

        do i = 1, size(wordsDict)
            if (wordsDict(i) == word1) then
                do j = 1, size(wordsDict)
                    if (wordsDict(j) == word2) then
                        dist = min(dist, i - j)
                    end if
                end do
            end if
        end do
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module shortest_distance

implicit none

contains

function shortest_distance(wordsDict, word1, word2) result(shortest_dist)

! Declare variables
integer :: i, j, k, shortest_dist
character(len=10) :: wordsDict(100000)
character(len=10) :: word1, word2

! Initialize variables
shortest_dist = 0

! Loop through the array of strings
do i = 1, size(wordsDict)

    ! Check if the current string is equal to word1
    if (wordsDict(i) == word1) then

        ! Set the starting index of word1
        j = i

    end if

    ! Check if the current string is equal to word2
    if (wordsDict(i) == word2) then

        ! Set the ending index of word2
        k = i

    end if

end do

! Check if both word1 and word2 were found in the array
if (j /= 0 .and. k /= 0) then

    ! Calculate the shortest distance between word1 and word2
    shortest_dist = abs(j - k)

end if

end function shortest_distance

end module

program main

use shortest_distance

implicit none

! Declare variables
integer :: i, j, k
character(len=10) :: wordsDict(100000)
character(len=10) :: word1, word2
integer :: shortest_dist

! Initialize variables
i = 1
j = 1
k = 1

! Read the input
read (*, *) wordsDict
read (*, *) word1
read (*, *) word2

! Call the shortest_distance function
shortest_dist = shortest_distance(wordsDict, word1, word2)

! Print the output
write (*, *) shortest_dist

end program
🌐 Data from online sources 
def shortestDistance(wordsDict, word1, word2):
    idx1, idx2, minDistance = -1, -1, float('inf')
    for i, word in enumerate(wordsDict):
        if word == word1:
            idx1 = i
        if word == word2:
            idx2 = i
        if idx1 != -1 and idx2 != -1:
            minDistance = min(minDistance, abs(idx1 - idx2))
    return minDistance

The algorithm iterates through the wordsDict list and uses two variables idx1 and idx2 to store the indices of the occurrences of word1 and word2. Initially, both indices are set to -1. In each iteration, if word1 or word2 is found, the corresponding index variable will be updated to store the current index.

After each index update, we check if both indices are not -1. If both indices are valid, the difference between the indices is computed, and minDistance is updated with the minimum value between the previously-stored minimum distance and the new distance.

Finally, the algorithm returns the value of minDistance, which represents the shortest distance between word1 and word2 in the wordsDict list.

🌐 Data from online sources 
#include <vector>
#include <string>
#include <climits>

int shortestDistance(std::vector<std::string> wordsDict, std::string word1, std::string word2) {
    int idx1 = -1, idx2 = -1, minDistance = INT_MAX;
    for (int i = 0; i < wordsDict.size(); i++) {
        if (wordsDict[i] == word1) idx1 = i;
        if (wordsDict[i] == word2) idx2 = i;
        if (idx1 != -1 && idx2 != -1)
            minDistance = std::min(minDistance, std::abs(idx1 - idx2));
    }
    return minDistance;
}

The algorithm iterates through the wordsDict list and uses two variables idx1 and idx2 to store the indices of the occurrences of word1 and word2. Initially, both indices are set to -1. In each iteration, if word1 or word2 is found, the corresponding index variable will be updated to store the current index.

After each index update, we check if both indices are not -1. If both indices are valid, the difference between the indices is computed, and minDistance is updated with the minimum value between the previously-stored minimum distance and the new distance.

Finally, the algorithm returns the value of minDistance, which represents the shortest distance between word1 and word2 in the wordsDict list.