LeetCode 2515: Shortest Distance to Target String in a Circular Array

Explanation

To solve this problem, we can iterate through the circular array of words starting from the given startIndex. For each step in either direction (next or previous), we calculate the minimum distance to reach the target string. We keep track of the minimum distance seen so far and return it as the final answer.

Here are the steps:

1. Initialize minDistance to a large number and set found flag to false.
2. Iterate through the circular array starting from startIndex.
3. For each position, calculate the distance to the target string in both directions (next and previous).
4. Update minDistance with the minimum of the previous minimum distance and the newly calculated distances.
5. If the target string is found at any position, set found flag to true.
6. Finally, return -1 if the target string was not found, else return the minDistance.

The time complexity of this solution is O(N) where N is the number of words in the array. The space complexity is O(1) as we are using constant extra space.

class Solution {
    public int shortestDistance(String[] words, String target, int startIndex) {
        int n = words.length;
        int minDistance = Integer.MAX_VALUE;
        boolean found = false;

        for (int i = 0; i < n; i++) {
            if (words[i].equals(target)) {
                found = true;
                int distance = Math.min(Math.abs(i - startIndex), n - Math.abs(i - startIndex));
                minDistance = Math.min(minDistance, distance);
            }
        }

        return found ? minDistance : -1;
    }
}