到目标字符串的最短距离

难度: Easy

给你一个下标从 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 个单位，到达下标 3 。
- 向左移动 1 个单位，到达下标 3 。
到达 "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

Submission

运行时间: 19 ms

内存: 16.2 MB

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        x = y = 0
        s = startIndex
        while words[s] != target:
            s += 1
            x += 1
            if s >= len(words):
                s = 0
            if x >= len(words):
                return -1
        s = startIndex
        while words[s] != target:
            s -= 1
            y += 1
            if s < 0:
                s = len(words)-1
        return min(x, y)

Explain

题解首先初始化两个计数器x和y分别表示向右和向左查找目标字符串target的距离。从startIndex开始，首先向右循环遍历words数组，每次移动后增加x的计数。如果索引s超过数组长度，则将其重置为0，模拟环形数组的行为。如果向右的遍历次数x超过数组长度而还未找到目标，则返回-1，表示target不在数组中。完成向右的遍历后，同样的方法向左遍历，每次递减索引s，并增加计数器y。向左遍历时如果索引s变为负数，则重置为数组的最后一个元素，再次模拟环形数组。最后，函数返回x和y中的较小值，即为到达target的最短距离。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        x = y = 0  # x记录向右查找的步数，y记录向左查找的步数
        s = startIndex  # 从startIndex开始搜索
        while words[s] != target:  # 向右搜索target
            s += 1  # 向右移动
            x += 1  # 增加步数
            if s >= len(words):  # 如果超出数组范围则环绕
                s = 0
            if x >= len(words):  # 如果搜索步数超过数组长度，表示未找到target
                return -1
        s = startIndex  # 重置起始位置，开始向左搜索
        while words[s] != target:  # 向左搜索target
            s -= 1  # 向左移动
            y += 1  # 增加步数
            if s < 0:  # 如果索引为负，则环绕到数组末尾
                s = len(words)-1
        return min(x, y)  # 返回最小的步数

Explore

题解中的方法确实考虑了环形数组的特性，通过将索引重置为0来模拟环形行为。然而，设置如果遍历次数超过数组长度就返回-1的逻辑，其实是基于一个假设：如果在整个数组中都没有找到`target`，那么即使继续环绕搜索也是无效的。这是因为一旦遍历的次数等于数组长度，意味着已经检查过数组中的每一个元素。如果在这个过程中都没有找到目标，那么继续遍历也不会找到。所以，这不是忽视了环形数组的特性，而是一种避免无效搜索的优化措施。

将索引s直接调整到数组末尾，而不使用`(s - 1 + n) % n`的方式，本质上是两种不同的实现方式，但都能正确处理索引环绕的情况。直接设置`s = len(words) - 1`在这种情况下简化了计算，避免了每次都进行取模运算，可能在某些情况下提高了效率。不过，使用`(s - 1 + n) % n`的方式具有更好的通用性和可读性，对于维护和理解代码是有帮助的。选择哪种方式，取决于程序员对效率和代码可维护性的考量。

使用两个独立的while循环确实有可能导致对某些元素的重复计算，尤其是如果`target`接近`startIndex`时。通过一次遍历同时计算两个方向的距离是可能的，可以通过同时维护两个方向的索引和计数器来实现。这样的实现可以减少遍历次数，提高效率。例如，可以从`startIndex`出发，同时向左和向右扩展，每步更新两个方向的索引和距离计数器，直到找到`target`。这样的方法能够减少不必要的重复计算，尤其是在`target`位置距离`startIndex`较近时更为高效。