# 821. 字符的最短距离

<https://leetcode-cn.com/problems/shortest-distance-to-a-character>

## 题目描述

```
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

示例 1:

输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
说明:

- 字符串 S 的长度范围为 [1, 10000]。
- C 是一个单字符，且保证是字符串 S 里的字符。
- S 和 C 中的所有字母均为小写字母。

```

## 前置知识

* 数组的遍历(正向遍历和反向遍历)

## 思路

这道题就是让我们求的是向左或者向右距离目标字符最近的距离。

我画了个图方便大家理解：

![](https://p.ipic.vip/l1pccw.jpg)

比如我们要找第一个字符 l 的最近的字符 e，直观的想法就是向左向右分别搜索，遇到字符 e 就停止，比较两侧的距离，并取较小的即可。如上图，l 就是 3，c 就是 2。

这种直观的思路用代码来表示的话是这样的：

Python Code:

```py
class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        ans = []

        for i in range(len(S)):
            # 从 i 向左向右扩展
            l = r = i
            # 向左找到第一个 C
            while l > -1:
                if S[l] == C: break
                l -= 1
            # 向左找到第一个 C
            while r < len(S):
                if S[r] == C: break
                r += 1
            # 如果至死没有找到，则赋值一个无限大的数字，由于题目的数据范围是 [1, 10000]，因此 -10000 或者  10000就够了。
            if l == -1: l = -10000
            if r == len(S): r = 10000
            # 选较近的即可
            ans.append(min(r - i, i - l))
        return ans
```

**复杂度分析**

* 时间复杂度：$O(N^2)$
* 空间复杂度：$O(1)$

由于题目的数据范围是 $10^4$，因此通过所有的测试用例是没有问题的。

但是实际上，我们可以在线性的时间内解决。这里的关键点和上面的解法类似，也是两端遍历。不过不再是盲目的查找，因为这样做会有很多没有必要的计算。

我们可以使用空间换时间的方式来解，这里我使用类似单调栈的解法来解，大家也可以使用其他手段。关于单调栈的技巧，不在这里展开，感兴趣的可以期待我后面的专题。

```py
class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        ans = [10000] * len(S)
        stack = []
        for i in range(len(S)):
            while stack and S[i] == C:
                ans[stack.pop()] = i - stack[-1]
            if S[i] != C:stack.append(i)
            else: ans[i] = 0
        for i in range(len(S) - 1, -1, -1):
            while stack and S[i] == C:
                ans[stack.pop()] = min(ans[stack[-1]], stack[-1] - i)
            if S[i] != C:stack.append(i)
            else: ans[i] = 0

        return ans
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

实际上，我们根本不需要栈来存储。原因很简单，那就是每次我们碰到目标字符 C 的时候， 我们就把栈**全部清空**了，因此我们用一个变量标识即可，具体参考后面的代码区。

> 如果碰到目标字符 C 的时候，不把栈清空，那么这个栈的空间多半是不能省的，反之可以省。

## 代码

代码支持：Python3，Java, CPP, Go, PHP

Python3 Code：

```py
class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        pre = -10000
        ans = []

        for i in range(len(S)):
            if S[i] == C: pre = i
            ans.append(i - pre)
        pre = 20000
        for i in range(len(S) - 1, -1, -1):
            if S[i] == C: pre = i
            ans[i] = min(ans[i], pre - i)
        return ans
```

Java Code：

```java
class Solution {
    public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = -10000;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = i - prev;
        }

        prev = 20000;
        for (int i = N-1; i >= 0; --i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }
}
```

CPP Code:

```cpp
class Solution {
public:
   vector<int> shortestToChar(string S, char C) {
       vector<int> ans(S.size(), 0);
       int prev = -10000;
       for(int i = 0; i < S.size(); i ++){
           if(S[i] == C) prev = i;
           ans[i] = i - prev;
       }
       prev = 20000;
       for(int i = S.size() - 1; i >= 0; i --){
           if(S[i] == C) prev = i;
           ans[i] = min(ans[i], prev - i);
       }
       return ans;
   }
};
```

Go Code:

```go
func shortestToChar(S string, C byte) []int {
    N := len(S)
    ans := make([]int, N)

    pre := -N // 最大距离
    for i := 0; i < N; i++ {
        if S[i] == C {
            pre = i
        }
        ans[i] = i - pre
    }

    pre = N*2 // 最大距离
    for i := N - 1; i >= 0; i-- {
        if S[i] == C {
            pre = i
        }
        ans[i] = min(ans[i], pre-i)
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

PHP Code:

```php
class Solution
{

    /**
     * @param String $S
     * @param String $C
     * @return Integer[]
     */
    function shortestToChar($S, $C)
    {
        $N = strlen($S);
        $ans = [];

        $pre = -$N;
        for ($i = 0; $i < $N; $i++) {
            if ($S[$i] == $C) {
                $pre = $i;
            }
            $ans[$i] = $i - $pre;
        }

        $pre = $N * 2;
        for ($i = $N - 1; $i >= 0; $i--) {
            if ($S[$i] == $C) {
                $pre = $i;
            }
            $ans[$i] = min($ans[$i], $pre - $i);
        }
        return $ans;
    }
}
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/821.shortest-distance-to-a-character.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.