Shortest Distance to a Character

# 問題

文字列sと文字cが与えられる．次のような整数配列answerを返せ

len(answer) == len(s)
answer[i]は位置iから最も近いcまでの距離（インデックスの差の絶対値）

1
2
s = "loveleetcode", c = "e"
-> [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

# 解法

各iについて，左右を見て近いcを探せば良いのだが，これをそのまま書くのではなく，

各iの左側をまず見る
次に各iの右側を見る

と書くとよい．

1
2
3
4
5
   "l    o   v    e l e e t c o d e" (c = "e")
->) inf inf inf   0 1 0 0 1 2 3 4 0
     3   2   1    0 1 0 0 4 3 2 1 0 (<-
------------------------------------------------
-> [ 3   2   1    0 1 0 0 1 2 2 1 0] (min)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        N = len(s)
        ans = []

        prev = float("-inf")
        for i in range(0, N, 1):
            if s[i] == c:
                prev = i
            ans.append(i - prev)

        prev = float("+inf")
        for i in range(N-1, -1, -1):
            if s[i] == c:
                prev = i
            ans[i] = min(ans[i], prev - i)

        return ans

# 出典

https://leetcode.com/problems/shortest-distance-to-a-character/