Easy

题目描述

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

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

从 startIndex 开始，你可以向前或者向后移动，每次移动一步。

返回到达字符串 target 所需的最短距离。如果字符串 target 不存在于 words 中，返回 -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
解释：因为 "ate" 不存在于 words 中，所以返回 -1 。

约束条件：

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

解题思路

这是一道关于环形数组的简单遍历题。由于数组是环形的，我们可以向左或向右移动来寻找目标字符串。

核心思路：

  1. 首先检查目标字符串是否存在于数组中，不存在则返回 -1
  2. 遍历数组找到所有等于目标字符串的位置
  3. 对于每个目标位置，计算从起始位置到该位置的最短距离
  4. 在环形数组中，两点间的距离有两种计算方式：
    • 向右移动：(targetIndex - startIndex + n) % n
    • 向左移动：(startIndex - targetIndex + n) % n
  5. 取两种移动方式中的最小值

优化思路： 由于是环形数组，两点间的最短距离就是 min(顺时针距离, 逆时针距离)。对于任意两点，顺时针距离 + 逆时针距离 = 数组长度，所以最短距离不会超过 n/2。

我们可以直接计算距离并取最小值，无需分别考虑左右移动。

代码实现

class Solution {
public:
    int closestTarget(vector<string>& words, string target, int startIndex) {
        int n = words.size();
        int minDist = INT_MAX;
        
        for (int i = 0; i < n; i++) {
            if (words[i] == target) {
                int dist = min(abs(i - startIndex), n - abs(i - startIndex));
                minDist = min(minDist, dist);
            }
        }
        
        return minDist == INT_MAX ? -1 : minDist;
    }
};

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:
                dist = min(abs(i - startIndex), n - abs(i - startIndex))
                min_dist = min(min_dist, dist)
        
        return -1 if min_dist == float('inf') else min_dist

public class Solution {
    public int ClosestTarget(string[] words, string target, int startIndex) {
        int n = words.Length;
        int minDist = int.MaxValue;
        
        for (int i = 0; i < n; i++) {
            if (words[i] == target) {
                int dist = Math.Min(Math.Abs(i - startIndex), n - Math.Abs(i - startIndex));
                minDist = Math.Min(minDist, dist);
            }
        }
        
        return minDist == int.MaxValue ? -1 : minDist;
    }
}

var closestTarget = function(words, target, startIndex) {
    const n = words.length;
    let minDist = Infinity;
    
    for (let i = 0; i < n; i++) {
        if (words[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个数组一次，其中 n 是数组长度
空间复杂度O(1)只使用了常数个额外变量

相关题目