What is the best approach to solve the "Shortest Distance to Target String in a Circular Array" problem?

The best approach is to calculate the distances in both directions (left and right) and then choose the smaller one. Don't forget to handle the case where the target is not in the array.

How do I handle the circular nature of the array?

You can handle the circular nature by using modulo operations when calculating the distances, ensuring you correctly wrap around the array.

What if the target string doesn't exist in the array?

If the target string doesn't exist in the array, return -1 as per the problem's constraints.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of words in the array. You may need to check all words to find the target.

Can this problem be solved with a more efficient algorithm?

This problem is generally solved with a linear scan, but optimization could focus on early termination when the target is found or when distance calculations can be skipped.

#2515

Easy

auto_awesome数组·string

LeetCode 题解工作台

到目标字符串的最短距离

给你一个下标从 0 开始的环形字符串数组 words 和一个字符串 target 。环形数组意味着数组首尾相连。形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n…

数组字符串

题目描述

给你一个下标从 0 开始的环形字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。

形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。

从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。

返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。

示例 1：

输入：words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
输出：1
解释：从下标 1 开始，可以经由以下步骤到达 "hello" ：
- 向右移动 3 个单位，到达下标 4 。
- 向左移动 2 个单位，到达下标 4 。
- 向右移动 4 个单位，到达下标 0 。
- 向左移动 1 个单位，到达下标 0 。
到达 "hello" 的最短距离是 1 。

示例 2：

输入：words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
输出：1
解释：从下标 0 开始，可以经由以下步骤到达 "leetcode" ：
- 向右移动 2 个单位，到达下标 2 。
- 向左移动 1 个单位，到达下标 2 。
到达 "leetcode" 的最短距离是 1 。

示例 3：

输入：words = ["i","eat","leetcode"], target = "ate", startIndex = 0
输出：-1
解释：因为 words 中不存在字符串 "ate" ，所以返回 -1 。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 和 target 仅由小写英文字母组成
0 <= startIndex < words.length

lightbulb

解题思路

方法一：一次遍历

我们遍历数组 $\textit{words}$ ，找到与 $\textit{target}$ 相等的单词，计算其与 $\textit{startIndex}$ 的距离 $t$ ，则此时的最短距离为 $\min(t, n - t)$ ，我们只需要不断更新最小值即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def closestTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        ans = n
        for i, w in enumerate(words):
            if w == target:
                t = abs(i - startIndex)
                ans = min(ans, t, n - t)
        return -1 if ans == n else ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluating the candidate’s understanding of array traversal with circular properties.
question_mark
Looking for the ability to handle multiple path options and compare results efficiently.
question_mark
Testing edge case handling where the target string may not exist in the array.

warning

常见陷阱

外企场景

error
Failing to account for the circular nature of the array when calculating distances.
error
Overcomplicating the solution by unnecessarily checking for all possible paths, rather than focusing on the two directions.
error
Not handling the edge case where the target does not exist in the array, which could lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
A variant could involve considering distances in a non-circular array, simplifying the problem by eliminating the need to wrap around.
arrow_right_alt
You could extend the problem by introducing multiple targets and needing to find the shortest distance to any one of them.
arrow_right_alt
A more complex variant would involve adding constraints, such as having to pass through certain words before reaching the target.

help

常见问题

外企场景

继续练习

#2512 奖励最顶尖的 K 名学生 #2506 统计相似字符串对的数目 #2496 数组中字符串的最大值