字符的最短距离

难度: Easy

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。

两个下标 i 和 j 之间的距离为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

示例 2：

输入：s = "aaab", c = "b"
输出：[3,2,1,0]

提示：

1 <= s.length <= 10⁴
s[i] 和 c 均为小写英文字母
题目数据保证 c 在 s 中至少出现一次

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        answer = [0] * n
        prev = float('-inf')
        
        for i in range(n):
            if s[i] == c:
                prev = i
            answer[i] = i - prev
        
        prev = float('inf')
        for i in range(n-1, -1, -1):
            if s[i] == c:
                prev = i
            answer[i] = min(answer[i], prev - i)
        
        return answer

Explain

该题解使用了两次遍历的方法。第一次正向遍历字符串，记录每个位置距离左侧最近的字符 c 的距离。第二次反向遍历字符串，更新每个位置距离右侧最近的字符 c 的距离。最终答案取两次遍历结果的最小值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        answer = [0] * n  # 初始化结果数组
        prev = float('-inf')  # 初始化上一个字符 c 的位置为负无穷
        
        # 第一次正向遍历字符串
        for i in range(n):
            if s[i] == c:
                prev = i  # 更新上一个字符 c 的位置
            answer[i] = i - prev  # 记录当前位置距离左侧最近的字符 c 的距离
        
        prev = float('inf')  # 初始化上一个字符 c 的位置为正无穷
        # 第二次反向遍历字符串
        for i in range(n-1, -1, -1):
            if s[i] == c:
                prev = i  # 更新上一个字符 c 的位置
            answer[i] = min(answer[i], prev - i)  # 更新当前位置距离最近的字符 c 的距离
        
        return answer

Explore

在第一次遍历中，初始化prev为float('-inf')是为了处理字符串开头部分，在遇到第一个目标字符c之前的情况。由于此时尚未遇到任何字符c，使用float('-inf')可以确保计算出的距离足够大，从而在后续遇到字符c后能正确更新。类似地，第二次反向遍历初始化prev为float('inf')的目的是处理字符串尾部在遇到最后一个字符c之后的情况。这种初始化允许在计算距离时，如果尚未遇到字符c，能保持一个足够大的默认距离值，直至遇到字符c并进行更新。这样的初始化在逻辑上保证了在字符串的任一端如果没有字符c出现，该端的字符到c的距离被认为是无穷大，这有助于在实际遇到字符c时能够正确计算距离。

在第一次遍历后，answer数组中的每个元素已经包含了每个位置到最近左侧字符c的距离。第二次遍历的目的是更新这些距离值，以包括到最近右侧字符c的距离。使用min函数是因为我们需要取左侧和右侧字符c的最小距离。例如，假设字符串为'sabcb', 字符c为'b'。第一次遍历后，answer=[2, 1, 0, 1, 2]。第二次遍历更新时，尤其在索引2左右，距离左侧的'b'为0，距离右侧的'b'也为0，所以使用min函数来确保我们取这两个0中的最小值，保持正确的最小距离。如果不使用min函数，那么第二次遍历可能会错误地覆盖之前计算的有效距离值。

当字符串s的长度为1或字符c在字符串中只出现一次时，算法仍然有效，无需特别调整。对于长度为1的情况，无论字符是否为c，两次遍历都能正确计算距离（要么是0，要么是无穷大然后通过遍历得到正确的距离）。如果字符c只出现一次，第一次遍历将在字符c出现位置之前的所有位置设置很大的距离值，而在c之后的位置则正确计算相对于这唯一的c的距离，第二次遍历同理。因此，该方法自然地处理了这些边界情况，确保了算法的普适性和正确性。