字符的最短距离 图解题解

answer[i] 要算的是什么距离

给字符串 s 和字符 c（题目保证 c 在 s 里至少出现一次），要为每个下标 i 求它到最近那个 c 的距离，即下标差的绝对值 abs(i-j)。题面 s="loveleetcode"、c="e"，e 在下标 3、5、6、11，输出 [3,2,1,0,1,0,0,1,2,2,1,0]：是 e 的位置为 0，越远数越大。

每个位置都向两边找一遍，慢在哪

O(n²) 是这么来的：站在每位往左右各走一趟找最近的 c、取较近那段，这是最容易想到的暴力。s 有 n 个字符，每个位置最坏要扫遍整串才碰到 c，n 个位置各扫 n 步就是 O(n²)。串长上万就明显拖不动。

一个位置的最近 c，非左即右

对某个位置来说，离它最近的 c 要么在左边、要么在右边，取近的就是答案。可从左走时右边的 c 还没扫到，一遍只知一侧。于是分两遍：第一遍从左到右，求每位到左边最近 c 的距离；第二遍从右到左，求到右边最近 c 的距离；同一位置两个方向取 min，就是真正的最近距离。

pre、suf 两个变量怎么一路更新

先把答案数组每格填成 n（串长，是距离的上界）；pre 初始设成负无穷，表示左边还没出现过 c。第一遍从左往右：遇到 c 就把 pre 更新成当前下标，再让 ans[i] 取「原值」和「i 减 pre」里更小的。左边一直没 c 时 i 减 pre 是无穷大，那格保持上界，留给第二遍补。第二遍从右往左对称：遇到 c 更新 suf，ans[i] 再和「suf 减 i」取一次 min。两遍都用减法、方向保证非负，天然就是绝对值距离，不用再套 abs。

两遍扫过 loveleetcode，各得什么

第一遍从左，pre 记左边最近的 e：下标 0、1、2（lov）左边没 e，停在上界；下标 3 遇 e，pre=3、ans=0；下标 4 得 1；下标 5、6 遇 e，pre 更新为 5、6、两格 0；下标 7 到 10 依次 1、2、3、4；下标 11 遇 e，ans=0。

第二遍从右，suf 记右边最近的 e，取一次 min：下标 10、9 右距 1、2 比原来的 4、3 近，更新成 1、2；下标 8、7 右距 3、4 比原来的 2、1 远，保持 2、1；下标 6、5 遇 e 更新 suf；下标 4 得 1（与原相等）；下标 3 遇 e；下标 2、1、0 得 1、2、3，补上前三格。最终得到 [3,2,1,0,1,0,0,1,2,2,1,0]。

c 挤在串的一头，就全靠另一遍兜底

两遍都是从头到尾的线性遍历，时间 O(n)；除答案数组外只多用 pre、suf 两个变量，空间 O(1)。两个边界说明为什么少一遍就错：c 全挤在最右端（如 s="aaab"、c="b"），第一遍从左走时前面每个位置左边都没 b，左距全停在上界，答案全靠第二遍从右补出；c 在最左端就换第一遍兜底。另一个易错点：pre 别填 0，那等于假装下标 0 处有个 c，会把开头本该由另一遍补的位置压成错误小距离——填负无穷，才能把「还没遇到 c」和「距离真是 0」分开。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [n] * n
        pre = -inf
        for i, ch in enumerate(s):
            if ch == c:
                pre = i
            ans[i] = min(ans[i], i - pre)
        suf = inf
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                suf = i
            ans[i] = min(ans[i], suf - i)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        const int inf = 1 << 30;
        vector<int> ans(n, inf);
        for (int i = 0, pre = -inf; i < n; ++i) {
            if (s[i] == c) {
                pre = i;
            }
            ans[i] = min(ans[i], i - pre);
        }
        for (int i = n - 1, suf = inf; ~i; --i) {
            if (s[i] == c) {
                suf = i;
            }
            ans[i] = min(ans[i], suf - i);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        final int inf = 1 << 30;
        Arrays.fill(ans, inf);
        for (int i = 0, pre = -inf; i < n; ++i) {
            if (s.charAt(i) == c) {
                pre = i;
            }
            ans[i] = Math.min(ans[i], i - pre);
        }
        for (int i = n - 1, suf = inf; i >= 0; --i) {
            if (s.charAt(i) == c) {
                suf = i;
            }
            ans[i] = Math.min(ans[i], suf - i);
        }
        return ans;
    }
}