題目表述
難度：簡單

給定一個(gè)字符串 S 和一個(gè)字符 C。返回一個(gè)代表字符串 S 中每個(gè)字符到字符串 S 中的字符 C 的最短距離的數(shù)組。

樸素解法

1. 遍歷S，找到所有 C 的位置索引；
2. 遍歷S，找到同所有 C 的位置索引的距離，取最小值；

復(fù)雜度為

python 描述

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        index = [i for i in range(len(S)) if S[i] is C]
        
        if len(index) > 0:
            return [min([abs(i-j)  for j in index ])for i in range(len(S))]
        else:
            return [float('inf') for i in S]

雙指針解法

1. 設(shè)置 right、left 指針；
2. right 前進(jìn)，同時(shí)更新 right 與 C 的位置；
3. right 遇到 C 停下，等 left 指針追上 right，同時(shí)更新 left 與 C 的位置；
4. 重復(fù) 2、3 直到 right 到達(dá) S 末尾；

復(fù)雜度為

python 描述

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        left = 0
        result = [float('inf') for i in S]

        for right in range(0, len(S)):
            if S[right] is C:
                for i in range(left, right + 1):
                    result[i] = min(result[i], right - i)
                left = right
            elif S[left] is C:
                result[right] = min(result[right], right - left)

        return result