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

Input: You are given a circular string array `words` and a string `target`.

Example: words = ["good", "morning", "world", "good"], target = "good", startIndex = 2

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 100

• words[i] and target consist of only lowercase English letters

• 0 <= startIndex < words.length

Output: Return the minimum distance to reach the target string, or -1 if the target is not found in the array.

Example: Output: 1

Constraints:

• If the target does not exist in words, return -1.

Goal: We need to compute the shortest possible distance to the target string in the circular array starting from the given index.

Steps:

• Iterate over the words array to find all indices where the target exists.

• Calculate the distance from the startIndex to each of these indices.

• Compute the shortest circular distance by considering both left and right movements.

• Return the minimum distance, or -1 if the target is not found.

Goal: The problem constraints are provided in the input and output specification sections.

Steps:

• The array length and string length are within manageable limits.

• The target is guaranteed to be a lowercase English string.

Assumptions:

• The words array is non-empty and the target is always a lowercase string.

• The input startIndex is always a valid index.

• Input: words = ["good", "morning", "world", "good"], target = "good", startIndex = 2

• Explanation: Starting from index 2, the closest 'good' can be found at index 3 by moving 1 step to the left, or at index 0 by moving 3 steps to the right. The shortest distance is 1.

• Input: words = ["apple", "banana", "cherry"], target = "banana", startIndex = 0

• Explanation: The target 'banana' is directly at index 1, so the shortest distance is 1.

Approach: The goal is to compute the minimum distance to the target string in the circular words array starting from the given index.

Observations:

• The array is circular, which means that the distances should be calculated modulo the array size.

• We can calculate distances by moving both left and right from the start index.

• The key challenge is efficiently calculating the minimum distance in a circular array.

Steps:

• Find all indices where the target string is present in the array.

• For each index, calculate the distance from the start index considering both directions (left and right).

• Return the minimum distance from all possible movements, or -1 if no valid target is found.

Empty Inputs:

• The words array is non-empty by definition.

Large Inputs:

• Handle cases where the words array is at its maximum length (100).

Special Values:

• If the target string does not exist, return -1.

Constraints:

• Ensure the startIndex is within the bounds of the array.

int closetTarget(vector<string>& words, string target, int s) {
    int n = words.size(), ans = INT_MAX;
    
    for(int i = 0; i < n; i++) 
        if(words[i] == target) 
            ans = min(ans, min(abs(s - i), abs(n - abs(s - i)))); 
    
    return ans == INT_MAX ? -1 : ans;
}

1 : Function Definition

int closetTarget(vector<string>& words, string target, int s) {

Define the function `closetTarget`, which takes a vector of words, a target string, and a starting index `s`.

2 : Variable Initialization

    int n = words.size(), ans = INT_MAX;

Initialize the variable `n` to store the size of the words vector, and `ans` to store the minimum distance, initially set to the maximum integer value.

3 : Loop

This space is for the loop that will iterate over the words array.

4 : Loop Iteration

    for(int i = 0; i < n; i++)

A loop that iterates over each word in the `words` vector.

5 : Conditional Check

        if(words[i] == target)

Check if the current word matches the target word.

6 : Distance Calculation

            ans = min(ans, min(abs(s - i), abs(n - abs(s - i))));

Calculate the minimum of the current distance and the circular distance between the current index `i` and the starting index `s`, and update the result `ans`.

7 : Return Statement

    return ans == INT_MAX ? -1 : ans;

Return the minimum distance if a target word was found, otherwise return -1.

Best Case: O(n) where n is the number of words in the array.

Average Case: O(n) where n is the number of words in the array.

Worst Case: O(n) where n is the number of words in the array.

Description: We iterate over the array to find the target and compute distances.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant because we only store a few variables during computation.

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

Explore →