E2515.到目标字符串的最短距离

implementation, https://leetcode.cn/problems/shortest-distance-to-target-string-in-a-circular-array/

给你一个下标从 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

这个问题要求在环形数组中找到从 startIndex 到达目标字符串 target 的最短距离。由于数组是环形的，我们可以向左（逆时针）或向右（顺时针）移动。

解题思路

1. 遍历数组：遍历 words 数组中的每一个元素。
2. 匹配目标：如果当前元素 words[i] 等于 target。
3. 计算距离：
   • 在环形数组中，两个下标 $i$ 和 $j$ 之间的距离有两种走法：
     1. 直接相减的绝对值：$|i-j|$。
     2. 跨越首尾的距离：$n-|i-j|$（其中 $n$ 是数组长度）。
   • 这两者中的较小值即为从 startIndex 到当前下标 $i$ 的最短步数。
4. 更新最小值：在所有匹配到的下标中，记录这个最短步数的全局最小值。
5. 边界处理：如果遍历完整个数组都没有找到 target，则返回 -1。

代码实现

class Solution:
    def closestTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        # 初始化为一个不可能的大值，n 即可，因为最大距离不会超过 n-1
        min_dist = n
        
        found = False
        for i in range(n):
            if words[i] == target:
                found = True
                # 直接距离
                d1 = abs(i - startIndex)
                # 环形跨越首尾的距离
                d2 = n - d1
                
                # 取两者的最小值，并更新全局最小距离
                min_dist = min(min_dist, d1, d2)
        
        return min_dist if found else -1

复杂度分析

• 时间复杂度：$O(n\times L)$，其中 $n$ 是数组 words 的长度，$L$ 是字符串的平均长度。我们需要遍历一次数组，并且每次比较字符串需要 $O(L)$ 的时间。
• 空间复杂度：$O(1)$，除了存储输入的变量外，只使用了常数级别的额外空间。

示例分析 (示例 1)

输入：words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1

1. 数组长度 $n=5$。
2. 下标 $0$ 处是 "hello"：
   • 距离 $d1=|0-1|=1$
   • 距离 $d2=5-1=4$
   • 当前最短距离 = $min(1,4)=1$。
3. 下标 $4$ 处是 "hello"：
   • 距离 $d1=|4-1|=3$
   • 距离 $d2=5-3=2$
   • 当前最短距离 = $min(1,2)=1$。
4. 最终结果为 1。