Shortest Distance to Target String in a Circular Array

🏠 ⬅️ ➡️

You are given a 0-indexed circular string array words and a string target. A circular array means that the array's end connects to the array's beginning.

  • Formally, the next element of words[i] is words[(i + 1) % n] and the previous element of words[i] is words[(i - 1 + n) % n], where n is the length of words.

Starting from startIndex, you can move to either the next word or the previous word with 1 step at a time.

Return the shortest distance needed to reach the string target. If the string target does not exist in words, return -1.

Example 1:

Input: words = [ "hello ", "i ", "am ", "leetcode ", "hello "], target = "hello ", startIndex = 1 Output: 1 Explanation: We start from index 1 and can reach "hello " by - moving 3 units to the right to reach index 4. - moving 2 units to the left to reach index 4. - moving 4 units to the right to reach index 0. - moving 1 unit to the left to reach index 0. The shortest distance to reach "hello " is 1.

Example 2:

Input: words = [ "a ", "b ", "leetcode "], target = "leetcode ", startIndex = 0 Output: 1 Explanation: We start from index 0 and can reach "leetcode " by - moving 2 units to the right to reach index 3. - moving 1 unit to the left to reach index 3. The shortest distance to reach "leetcode " is 1.

Example 3:

Input: words = [ "i ", "eat ", "leetcode "], target = "ate ", startIndex = 0 Output: -1 Explanation: Since "ate " does not exist in words, we return -1.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] and target consist of only lowercase English letters.
  • 0 <= startIndex < words.length
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k, l, m, n
    character(len=100), dimension(:), allocatable :: words
    character(len=100) :: target
    integer :: startIndex
    integer :: result

    ! Examples
    allocate(words(5))
    words(1) = 'hello '
    words(2) = 'i '
    words(3) = 'am '
    words(4) = 'leetcode '
    words(5) = 'hello '
    target = 'hello '
    startIndex = 1
    result = shortestDistance(words, target, startIndex)
    write(*,*) 'Example 1:'
    write(*,*) 'words = ', words
    write(*,*) 'target = ', target
    write(*,*) 'startIndex = ', startIndex
    write(*,*) 'result = ', result

    deallocate(words)

    allocate(words(3))
    words(1) = 'a '
    words(2) = 'b '
    words(3) = 'leetcode '
    target = 'leetcode '
    startIndex = 0
    result = shortestDistance(words, target, startIndex)
    write(*,*) 'Example 2:'
    write(*,*) 'words = ', words
    write(*,*) 'target = ', target
    write(*,*) 'startIndex = ', startIndex
    write(*,*) 'result = ', result

    deallocate(words)

    allocate(words(3))
    words(1) = 'i '
    words(2) = 'eat '
    words(3) = 'leetcode '
    target = 'ate '
    startIndex = 0
    result = shortestDistance(words, target, startIndex)
    write(*,*) 'Example 3:'
    write(*,*) 'words = ', words
    write(*,*) 'target = ', target
    write(*,*) 'startIndex = ', startIndex
    write(*,*) 'result = ', result

contains

    function shortestDistance(words, target, startIndex) result(res)
        implicit none
        character(len=*), dimension(:), intent(in) :: words
        character(len=*), intent(in) :: target
        integer, intent(in) :: startIndex
        integer :: res

        integer :: i, j, k, l, m, n
        logical :: found

        res = -1
        found = .false.
        do i = 1, size(words)
            if (words(i) == target) then
                found = .true.
                exit
            end if
        end do

        if (.not. found) return

        res = 0
        do while (.true.)
            if (words(startIndex) == target) then
                exit
            end if

            if (startIndex == 0) then
                startIndex = size(words)
            else
                startIndex = startIndex - 1
            end if

            res = res + 1
        end do

    end function shortestDistance

end program main
❌ Compiled
❌ Executed
❌ Correct 
module shortest_distance_to_target

implicit none

contains

function shortest_distance(words, target, start_index) result(distance)

! Declare the variables
integer, dimension(size(words)) :: next_index, prev_index
integer :: distance, n, i, j, k
character(len=*), dimension(size(words)) :: words
character(len=*) :: target
integer :: start_index

! Initialize the variables
n = size(words)
distance = -1

! Find the next and previous indices of the target word
do i = 1, n
    if (words(i) == target) then
        next_index(i) = (i + 1) % n
        prev_index(i) = (i - 1 + n) % n
        distance = 0
        exit
    end if
end do

! If the target word is not found, return -1
if (distance == -1) then
    return
end if

! Find the shortest distance to the target word
do i = 1, n
    do j = 1, n
        if (words(i) == words(j)) then
            do k = 1, n
                if (words(k) == target) then
                    distance = min(distance, abs(i - k) + abs(j - k))
                    exit
                end if
            end do
        end if
    end do
end do

end function shortest_distance

end module

! Test the shortest_distance function with the given examples
program test_shortest_distance

use shortest_distance_to_target

implicit none

! Declare the variables
integer, parameter :: n = 5
character(len=10), dimension(n) :: words
character(len=10) :: target
integer :: start_index, distance

! Test case 1:
words = ["hello ", "i ", "am ", "leetcode ", "hello "]
target = "hello "
start_index = 1
distance = shortest_distance(words, target, start_index)
write (*,*) "Test case 1: ", distance

! Test case 2:
words = ["a ", "b ", "leetcode "]
target = "leetcode "
start_index = 0
distance = shortest_distance(words, target, start_index)
write (*,*) "Test case 2: ", distance

! Test case 3:
words = ["i ", "eat ", "leetcode "]
target = "ate "
start_index = 0
distance = shortest_distance(words, target, start_index)
write (*,*) "Test case 3: ", distance

end program
🌐 Data from online sources 
def shortest_distance(words, target, startIndex):
    n = len(words)
    left, right, i = 0, 0, startIndex
    while True:
        if words[i] == target:
            return min(left, right)
        left += 1
        right += 1
        i = (i + 1) % n
        if left == n:
            break
    return -1

The algorithm initializes the variables left, right, and i to count the minimum steps taken to reach the target string. It starts searching from the startIndex and iterates in a circular manner with the help of the modulo operator. When the word at the current index i matches the target, the minimum of left and right is returned as the shortest distance. If no matching word is found after the entire traversal, the algorithm returns -1. The reason for maintaining both left and right counters is that we are allowed to move in both directions (previous or next) from the startIndex. Both left and right counters are incremented in each iteration for every step taken during the search.

The code provided above is directly focused on solving the given problem, looping over until either the target is found or the traversal is complete, and in each language, the syntax is adapted to match the respective language conventions. The logic and algorithm stay the same across all languages.

🌐 Data from online sources 
int shortest_distance(vector<string>& words, string target, int startIndex) {
    int n = words.size();
    int left = 0, right = 0, i = startIndex;
    while (true) {
        if (words[i] == target) {
            return min(left, right);
        }
        left++;
        right++;
        i = (i + 1) % n;
        if (left == n) {
            break;
        }
    }
    return -1;
}

The algorithm initializes the variables left, right, and i to count the minimum steps taken to reach the target string. It starts searching from the startIndex and iterates in a circular manner with the help of the modulo operator. When the word at the current index i matches the target, the minimum of left and right is returned as the shortest distance. If no matching word is found after the entire traversal, the algorithm returns -1. The reason for maintaining both left and right counters is that we are allowed to move in both directions (previous or next) from the startIndex. Both left and right counters are incremented in each iteration for every step taken during the search.

The code provided above is directly focused on solving the given problem, looping over until either the target is found or the traversal is complete, and in each language, the syntax is adapted to match the respective language conventions. The logic and algorithm stay the same across all languages.