字符的最短距离
给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。 两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。 来源：力扣（LeetCode）
AC代码class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
answer = [0] * len(s)
flag = []
for i, l in enumerate(s):
if l == c:
flag.append(i)
if len(flag) == 1:
return [abs(i - flag[0]) for i in range(len(s))]
else:
for i, f in enumerate(flag):
if i == 0:
for j in range(flag[0]):
answer[j] = flag[0] - j
else:
for j in range(flag[i - 1] + 1, flag[i]):
answer[j] = min(j - flag[i - 1], flag[i] - j)
if i == len(flag) - 1:
for j in range(flag[-1] + 1, len(answer)):
answer[j] = j - flag[-1]
return answer
最开始想尝试复杂度O（n）空间复杂度O（1）的方法，一次遍历解决，后面感觉不合理，改成如上做法。主要思路为： 1、遍历整个字符串，得到所有字符c的索引位置； 2、遍历索引列表，第一个索引的左侧为由大到小，中间应考虑两边的最小值，最后一个索引右侧为由小到大；
官方代码class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
n = len(s)
ans = [0] * n
idx = -n
for i, ch in enumerate(s):
if ch == c:
idx = i
ans[i] = i - idx
idx = 2 * n
for i in range(n - 1, -1, -1):
if s[i] == c:
idx = i
ans[i] = min(ans[i], idx - i)
return ans
# 作者：LeetCode-Solution。
进行两次遍历，一遍看左，一遍看右。和笔者最开始的想法是类似的，但是看来官方解法也需要遍历两遍
