821.md

Shortest Distance to a Character

Description

link

---

Solution : DP

• 循环两次即可，一次从前往后一次从后往前

---

Code

Complexity T : O(N) M : O(N)

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        n, pos = len(S), -float('inf')
        res = [n] * n
        for i in list(range(n)) + list(range(n)[::-1]):
            if S[i] == C:
                pos = i
            res[i] = min(res[i], abs(i - pos))
        return res