# 【基础篇 - Day 2】 2020-11-02 - 821. 字符的最短距离（01. 数组，栈，队列 ）
# 题目描述
给定一个字符串 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 中的所有字母均为小写字母。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shortest-distance-to-a-character 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(n^2)
空间复杂度: O(1)
var shortestToChar = function (S, C) {
let arr = []
for (let i = 0; i < S.length; i++) {
if (S[i] === C) {
arr.push(0)
continue
}
let l = i, r = i, short = Infinity
while (l >= 0) {
if (S[l] === C) {
short= Math.min(short, i - l)
break
}
l--
}
while (r < S.length) {
if (S[r] === C) {
short=Math.min(short, r - i)
break
}
r++
}
arr.push(short)
}
return arr
};
# 解法二
# 时空复杂度
时间复杂度：O(n)
空间复杂度: O(1)
双向遍历一遍，第二次遍历的时候进行值比较
var shortestToChar = function (S, C) {
let arr = Array(S.length)
for (let i = 0; i < S.length; i++) {
if (S[i] === C) arr[i] = 0
else arr[i] = arr[i - 1] === void 0 ? Infinity : arr[i - 1] + 1
}
for (let i = S.length - 1; i >= 0; i--) {
if (arr[i] === Infinity || arr[i + 1] + 1 < arr[i]) arr[i] = arr[i + 1] + 1
}
return arr
};