LeetCode-821-字符的最短距离

解题思路：

1. 常规解法：先遍历一遍找到S中等于C的下标，再遍历一次S计算最短距离；
2. 指针双向遍历：当S中s等于C时，用指针从右往左和从左往右分别遍历，更新距离，其中从右往左遍历可以从s左边最近的一个C的位置开始遍历。

Python3代码：

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        # 指针双向遍历
        ans = [1e9]*len(S)
        for i in range(len(S)):
            if S[i] == C:
                left=i
                dis = 0
                while left>=0 and ans[left]>dis:
                    ans[left] = dis
                    left-=1
                    dis+=1
                right=i+1
                dis=1
                while right<len(S) and ans[right]>dis:
                    ans[right]=dis
                    right+=1
                    dis+=1
        return ans

        # 常规解法
        l = [i for i in range(len(S)) if S[i] ==C]
        ans=[0]*len(S)
        for i in range(len(S)):
            if S[i]==C:
                ans[i]=0
            else:
                ans[i]= min([abs(i-j) for j in l])
        return ans