共计 5010 个字符，预计需要花费 13 分钟才能阅读完成。
- 作者：小漾
- 起源：https://github.com/suukii/91-…
大家好，我是 lucifer，家喻户晓，我是一个小前端 (不是)。其实，我是 lucifer 的 1379 号迷妹观察员，我是一粒纳米前端。(不要答复，不要答复，不要答复！！！)
这是第一次投稿，所以能够废话几句，说一下我为什么做题和写题解。刚开始做算法题的时候，只是纯正感觉好玩，所以不仅没有刷题打算，写题解也只是轻易记下几笔，几个月后本人也看不懂的那种。一次偶尔机会发现了 lucifer 的明星题解仓库，是找到了 onepiece 的感觉。受他的启发，我也开始写些尽量能让人看懂的题解，尽管还赶不上 lucifer，但跟本人比总算是有了些提高。
身为迷妹观察员，lucifer 的 91 天学算法当然是不能错过的流动，当初流动的第二期正在 ???? 热进行中，有趣味的同学理解一下呀。言归正传，跟着 91 课程我不再是漫无目的，而是打算清晰，依照课程安顿的专题来做题，这样不仅更有利于理解某一类题波及的相干常识，还能相熟这类题的套路，再次遇见类似题型也能更快有思路。
废话就这么多，以下是注释局部。等等，还有最初一句，下面的 ” 不要答复 ” 是个三体梗，不晓得有没有人 GET 到我。
明天给大家带来一道力扣简略题，官网题解只给出了一种最优解。本文比拟贪婪，打算带大家用 四种姿态 来解决这道题。
<!– more –>
题目形容
题目地址：https://leetcode-cn.com/probl…
给定一个字符串 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 中的所有字母均为小写字母。解法 1：核心扩大法
思路
这是最合乎直觉的思路，对每个字符别离进行如下解决：
- 从以后下标登程，别离向左、右两个方向去寻找指标字符
C。 - 只在一个方向找到的话，间接计算字符间隔。
- 两个方向都找到的话，取两个间隔的最小值。
复杂度剖析
咱们须要对每一个元素都进行一次扩大操作，因而工夫复杂度就是 $N$ * 向两边扩大的总工夫复杂度。
而最坏的状况是指标字符 C 在字符串 S 的左右两个端点地位，这个时候工夫复杂度是 $O(N)$，因而总的工夫复杂度就是 $O(N^2)$
- 工夫复杂度：$O(N^2)$，N 为 S 的长度。
- 空间复杂度：$O(1)$。
代码
JavaScript Code
/**
* @param {string} S
* @param {character} C
* @return {number[]}
*/
var shortestToChar = function (S, C) {
// 后果数组 res
var res = Array(S.length).fill(0);
for (let i = 0; i < S.length; i++) {
// 如果以后是指标字符，就什么都不必做
if (S[i] === C) continue;
// 定义两个指针 l, r 别离向左、右两个方向寻找指标字符 C，取最短距离
let l = i,
r = i,
shortest = Infinity;
while (l >= 0) {if (S[l] === C) {shortest = Math.min(shortest, i - l);
break;
}
l--;
}
while (r < S.length) {if (S[r] === C) {shortest = Math.min(shortest, r - i);
break;
}
r++;
}
res[i] = shortest;
}
return res;
};解法 2：空间换工夫
思路
空间换工夫是编程中很常见的一种 trade-off (反过来，工夫换空间也是)。
因为指标字符 C 在 S 中的地位是不变的，所以咱们能够提前将 C 的所有下标记录在一个数组 cIndices 中。
而后遍历字符串 S 中的每个字符，到 cIndices 中找到间隔以后地位最近的下标，计算间隔。
复杂度剖析
和下面办法相似，只是向两边扩大的动作变成了线性扫描 cIndices，因而工夫复杂度就是 $N$ * 线性扫描 cIndices的工夫复杂度。
- 工夫复杂度：$O(N*K)$，N 是 S 的长度，K 是字符
C在字符串中呈现的次数。因为 $K <= N$。因而工夫上肯定是优于下面的解法的。 - 空间复杂度：$O(K)$，K 为字符
C呈现的次数，这是记录字符C呈现下标的辅助数组耗费的空间。
实际上，因为 cIndices 是一个枯燥递增的序列，因而咱们能够应用二分来确定最近的 index，工夫能够优化到 $N*logK$，这个就留给各位来解决吧。如果对二分不相熟的，能够看看我往期的《二分专题》
代码
JavaScript Code
/**
* @param {string} S
* @param {character} C
* @return {number[]}
*/
var shortestToChar = function (S, C) {
// 记录 C 字符在 S 字符串中呈现的所有下标
var cIndices = [];
for (let i = 0; i < S.length; i++) {if (S[i] === C) cIndices.push(i);
}
// 后果数组 res
var res = Array(S.length).fill(Infinity);
for (let i = 0; i < S.length; i++) {
// 指标字符，间隔是 0
if (S[i] === C) {res[i] = 0;
continue;
}
// 非指标字符，到下标数组中找最近的下标
for (const cIndex of cIndices) {const dist = Math.abs(cIndex - i);
// 小小剪枝一下
// 注：因为 cIndices 中的下标是递增的，前面的 dist 也会越来越大，能够排除
if (dist >= res[i]) break;
res[i] = dist;
}
}
return res;
};解法 3：贪婪
思路
其实对于每个字符来说，它只关怀离它最近的那个 C 字符，其余的它都不论。所以这里还能够用贪婪的思路：
- 先
从左往右遍历字符串S，用一个数组 left 记录每个字符左侧呈现的最初一个C字符的下标； - 再
从右往左遍历字符串S，用一个数组 right 记录每个字符右侧呈现的最初一个C字符的下标； - 而后同时遍历这两个数组，计算间隔最小值。
优化 1
再多想一步，其实第二个数组并不需要。因为对于左右两侧的 C 字符，咱们也只关怀其中间隔更近的那一个，所以第二次遍历的时候能够看状况笼罩掉第一个数组的值：
- 字符左侧没有呈现过
C字符 i - left>right - i(i 为以后字符下标，left 为字符左侧最近的C下标，right 为字符右侧最近的C下标)
如果呈现以上两种状况，就能够进行笼罩，最初再遍历一次数组计算间隔。
优化 2
如果咱们是间接记录 C 与以后字符的间隔，而不是记录 C 的下标，还能够省掉最初一次遍历计算间隔的过程。
复杂度剖析
下面我说了要开拓一个数组。而实际上题目也要返回一个数组，这个数组的长度也恰好是 $N$，这个空间是不可避免的。因而咱们间接利用这个数组，而不须要额定开拓空间，因而这里空间复杂度是 $O(1)$，而不是 $O(N)$，具体能够看下方代码区。
- 工夫复杂度：$O(N)$，N 是 S 的长度。
- 空间复杂度：$O(1)$。
代码
JavaScript Code
/**
* @param {string} S
* @param {character} C
* @return {number[]}
*/
var shortestToChar = function (S, C) {var res = Array(S.length);
// 第一次遍历：从左往右
// 找到呈现在左侧的 C 字符的最初下标
for (let i = 0; i < S.length; i++) {if (S[i] === C) res[i] = i;
// 如果左侧没有呈现 C 字符的话，用 Infinity 进行标记
else res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1];
}
// 第二次遍历：从右往左
// 找出当初右侧的 C 字符的最初下标
// 如果左侧没有呈现过 C 字符，或者右侧呈现的 C 字符间隔更近，就更新 res[i]
for (let i = S.length - 1; i >= 0; i--) {if (res[i] === Infinity || res[i + 1] - i < i - res[i]) res[i] = res[i + 1];
}
// 计算间隔
for (let i = 0; i < res.length; i++) {res[i] = Math.abs(res[i] - i);
}
return res;
};间接计算间隔：
JavaScript Code
/**
* @param {string} S
* @param {character} C
* @return {number[]}
*/
var shortestToChar = function (S, C) {var res = Array(S.length);
for (let i = 0; i < S.length; i++) {if (S[i] === C) res[i] = 0;
// 记录间隔：res[i - 1] + 1
else res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1] + 1;
}
for (let i = S.length - 1; i >= 0; i--) {// 更新间隔：res[i + 1] + 1
if (res[i] === Infinity || res[i + 1] + 1 < res[i]) res[i] = res[i + 1] + 1;
}
return res;
};Python Code:
class Solution:
def shortestToChar(self, S: str, C: str) -> List[int]:
pre = -len(S)
ans = []
for i in range(len(S)):
if S[i] == C: pre = i
ans.append(i - pre)
pre = len(S) * 2
for i in range(len(S) - 1, -1, -1):
if S[i] == C: pre = i
ans[i] = min(ans[i], pre - i)
return ans解法 4：窗口
思路
把 C 看成分界线，将 S 划分成一个个窗口。而后对每个窗口进行遍历，别离计算每个字符到窗口边界的间隔最小值，并在遍历的过程中更新窗口信息即可。
复杂度剖析
因为更新窗口里的“搜寻”下一个窗口的操作 总共 只须要 $N$ 次，因而工夫复杂度依然是 $N$，而不是 $N^2$。
- 工夫复杂度：$O(N)$，N 是 S 的长度。
- 空间复杂度：$O(1)$。
代码
JavaScript Code
/**
* @param {string} S
* @param {character} C
* @return {number[]}
*/
var shortestToChar = function (S, C) {
// 窗口左边界，如果没有就初始化为 Infinity
let l = S[0] === C ? 0 : Infinity,
// 窗口右边界
r = S.indexOf(C, 1);
const res = Array(S.length);
for (let i = 0; i < S.length; i++) {
// 计算字符到以后窗口左右边界的最小间隔
res[i] = Math.min(Math.abs(i - l), Math.abs(r - i));
// 遍历完了以后窗口的字符后，将整个窗口右移
if (i === r) {
l = r;
r = S.indexOf(C, l + 1);
}
}
return res;
};小结
本文给大家介绍了这道题的四种解法，从直觉思路动手，到应用空间换工夫的策略，再到贪婪算法思维，最初是一个简略直白，同时复杂度也是最优的思路。
对于刚开始做题的人来说，” 做进去 ” 是首要任务，但如果你有余力的话，也能够试试这样 ” 一题多解 ”，多锤炼一下本人。
但无论怎样，只有你对算法感兴趣，肯定要思考关注 lucifer 这个算法灯塔哦。不要嫌我啰嗦，真话不啰嗦。
更多题解能够拜访：https://github.com/suukii/91-days-algorithm
end
大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 37K star 啦。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
我整顿的 1000 多页的电子书已限时收费下载，大家能够去我的公众号《力扣加加》后盾回复电子书获取。
