LeetCode 2515：在环形数组中找到到目标字符串的最短距离

LeetCode 2515在环形数组中找到到目标字符串的最短距离**标签**LeetCode | 算法 | 环形数组 | 双方向遍历 | Python**难度**简单目录题目描述解题思路核心分析算法步骤完整代码标准LeetCode格式代码逐行解析示例运行验证复杂度分析总结一、题目描述给你一个下标从0开始的环形字符串数组words和一个字符串target。环形数组意味着数组首尾相连。形式上words[i]的下一个元素是words[(i 1) % n]而words[i]的前一个元素是words[(i - 1 n) % n]其中n是words的长度。从startIndex开始你一次可以用 1 步移动到下一个或者前一个单词。返回到达目标字符串target所需的最短距离。如果words中不存在字符串target返回-1。二、解题思路2.1 核心分析数组是环形的向左走和向右走都能到达目标位置我们需要取最短路径。距离计算规则向右距离abs(i - startIndex)向左距离n - abs(i - startIndex)最短距离 两者中的较小值遍历逻辑遍历数组所有元素找到所有等于target的下标对每个匹配下标计算最短距离保留全局最小值边界无匹配目标 → 返回-12.2 算法步骤获取数组长度n初始化最短距离为一个极大值如float(inf)遍历数组每个下标i如果words[i] target计算向右距离d1 abs(i - startIndex)计算向左距离d2 n - d1当前最小距离cur min(d1, d2)更新全局最小距离遍历结束若最小距离仍为极大值 → 返回-1否则返回最小距离三、完整代码标准LeetCode格式LeetCode 2515 完整AC代码from typing import List class Solution: def closestTarget(self, words: List[str], target: str, startIndex: int) - int: n len(words) min_dist float(inf) # 遍历所有位置寻找目标字符串 for i in range(n): if words[i] target: # 计算顺时针/逆时针距离取最小值 d abs(i - startIndex) cur_min min(d, n - d) # 更新最短距离 if cur_min min_dist: min_dist cur_min # 如果没有找到目标返回-1 return min_dist if min_dist ! float(inf) else -1**说明**代码可直接复制粘贴到LeetCode提交无需修改已通过所有测试用例。四、代码逐行解析from typing import List导入类型注解用于指定列表类型符合Python代码规范LeetCode提交可省略但保留更易读。class Solution: def closestTarget(self, words: List[str], target: str, startIndex: int) - int:标准LeetCode类与方法定义输入参数和返回值类型明确便于理解代码功能。n len(words) min_dist float(inf)n存储数组长度用于后续环形距离计算避免重复调用len(words)提升效率。min_dist记录最短距离初始化为无穷大float(‘inf’)表示初始状态下未找到目标字符串。for i in range(n): if words[i] target:遍历数组每一个下标i判断当前下标对应的元素是否等于目标字符串target找到所有匹配位置。d abs(i - startIndex) cur_min min(d, n - d)d计算从起始下标startIndex到当前匹配下标i的正向距离向右/顺时针移动的步数。n - d计算从起始下标到当前匹配下标的反向距离向左/逆时针移动的步数利用环形数组特性。cur_min取正向和反向距离的最小值即当前匹配位置到起始位置的最短步数。if cur_min min_dist: min_dist cur_min将当前匹配位置的最短步数与全局最短距离min_dist对比更新全局最小值。return min_dist if min_dist ! float(inf) else -1遍历结束后判断min_dist是否仍为无穷大若为无穷大说明数组中无目标字符串返回-1否则返回全局最短距离。五、示例运行验证示例 1输入words [hello,i,am,leetcode,hello], targethello, startIndex1匹配位置0和4到下标0的距离min(abs(0-1), 5-1) min(1,4) 1到下标4的距离min(abs(4-1), 5-3) min(3,2) 2全局最短距离1✅与示例输出一致示例 2输入words [a,b,leetcode], targetleetcode, startIndex0匹配位置2距离min(abs(2-0), 3-2) min(2,1) 1✅与示例输出一致示例 3输入words [i,eat,leetcode], targetate数组中无匹配target的元素 → 返回-1✅与示例输出一致六、复杂度分析时间复杂度O ( n ) O(n)O(n)仅遍历一次数组n nn为数组words的长度遍历过程中所有操作均为常数时间无嵌套循环。空间复杂度O ( 1 ) O(1)O(1)仅使用常数个变量n、min_dist、i、d、cur_min不占用额外空间与数组长度无关。七、总结本题是环形数组最短路径的经典入门题难度简单核心考点集中在3点环形数组的距离计算核心公式min(正向距离, 总长度-正向距离)利用环形特性实现双向距离对比。遍历逻辑通过一次遍历找到所有目标位置逐个计算最短距离并更新全局最小值高效且易懂。边界处理需判断数组中是否存在目标字符串无匹配时返回-1避免遗漏异常情况。代码简洁高效时间复杂度和空间复杂度均达到最优适合入门新手练习环形数组相关题型也可直接用于LeetCode提交。