Leetcode 821. Shortest Distance to a Character

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Shortest Distance to a Character

2. Solution

解析:Version 1,使用leftright分别记录当前字符的左右c的位置,左边没有为-1,右边没有为length。先初始化leftright,循环计算时,如果当前位置索引大于right,则对leftright进行更新,更新之后计算距离即可。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
length = len(s)
res = [0] * length
left = -1
right = 0
while s[right] != c:
right += 1
for i in range(length):
if right < i:
left = right
right += 1
while right < length and s[right] != c:
right += 1
if left < 0:
res[i] = right - i
elif right >= length:
res[i] = i - left
else:
res[i] = min(i - left, right - i)
return res

解析:Version 2,从左到右遍历数组,记录最左边字符c的位置,依次更新距离,从右往左遍历数组,记录最右边字符c的位置,依次更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
length = len(s)
res = [float('inf')] * length
left = -1
for i in range(length):
if s[i] == c:
left = i
if left > -1:
res[i] = min(res[i], i - left)
right = length
for i in range(length-1, -1, -1):
if s[i] == c:
right = i
if right < length:
res[i] = min(res[i], right - i)
return res

Reference

  1. https://leetcode.com/problems/shortest-distance-to-a-character/
如果有收获,可以请我喝杯咖啡!