821.字符的最短距离.md

题目链接

双向遍历

基本概念

思路

只遍历一次是不能解决问题的，当从左到右遍历时，只能算出当前字符距离左侧目标字符的距离，不知道右侧的，无法比较取最小值。所以需要遍历两次，一次正向遍历，一次反向遍历。

步骤：

1. 创建一个结果数组ans，正向遍历一次，记录上一次获取目标字符的位置preMatch，存储当前字符距离上次目标字符的距离i - preMatch；
2. 反向遍历一次，获取距离目标字符的距离，和上一次计算出的距离比较，取最小值；
3. 返回结果数组ans。

图解

假设字符串s为："hellow"，字符c为："l"。

第一次循环：

第二次循环：

代码

function shortestToChar(s: string, c: string): number[] {
    let ans = [];
    let prevMatch = Number.MIN_SAFE_INTEGER; // 定义为最小值

    // 正向遍历
    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            prevMatch = i;  // 记录目标字符的位置
        }
       // 因为 i >= prevMatch 的，所以直接减肯定为正数，算出距离；当prevMatch为MIN_SAFE_INTEGER时，减完是一个很大的值
        ans[i] = i - prevMatch;
    }

    prevMatch = Number.MAX_SAFE_INTEGER; // 定义为最大值
    // 反向遍历
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === c) {
            prevMatch = i; // 记录目标字符的位置
        }
        ans[i] = Math.min(prevMatch - i, ans[i]); // 和正向遍历的比较，取最小的位置作为最后的值
    }

    return ans;
};

优化版

这里还可以优化一下，不使用额外变量preMatch存储上次的目标字符串，另外赋值逻辑也有点变化。

图解

假设字符串s为："hellow"，字符c为："l"。

代码

function shortestToChar(s: string, c: string): number[] {
    const { length } = s;
    let ans = new Array(length).fill(length - 1); // 初始化，全部赋值为最大距离

    // 正向遍历
    ans[0] = s[0] === c ? 0 : ans[0]; // 边界值处理
    for (let i = 1; i < length; i++) { // 从1开始防减1溢出
        ans[i] = s[i] !== c ? ans[i - 1] + 1 : 0; // 如果是目标字符，直接赋值0，否则取上一个字符的距离加1
    }

    // 反向遍历
    ans[length - 1] = s[length - 1] === c ? 0 : ans[length - 1]; // 边界值处理
    for (let i = length - 2; i >= 0; i--) { // 从length - 2开始，防止加1溢出
        // 如果是目标字符，直接赋值0，否则取上一个字符的距离加1，再和上次记录的值作比较，取最小值
        ans[i] = Math.min(ans[i], s[i] !== c ? ans[i + 1] + 1 : 0);
    }

    return ans;
};