思路
1园细、使用一個數(shù)組記錄c的位置
2、雙指針懊悯,比較pos_c_index和pos_c_index下一個位置的abs的結(jié)果
代碼
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
# 先使用一個數(shù)組記錄c的位置凛捏,雙指針
pos_c = []
for i in range(len(s)):
if s[i] == c:
pos_c.append(i)
dis_res = []
pos_c_index = 0
for i in range(len(s)):
if pos_c_index + 1 < len(pos_c):
if abs(i - pos_c[pos_c_index]) <= abs(i - pos_c[pos_c_index + 1]):
dis_res.append(abs(i - pos_c[pos_c_index]))
else:
dis_res.append(abs(i - pos_c[pos_c_index + 1]))
pos_c_index += 1
else: # pos_c_index在最后一個位置
dis_res.append(abs(i - pos_c[pos_c_index]))
return dis_res
復(fù)雜度
時間復(fù)雜度:o(n)
空間復(fù)雜度:o(n)->o(k),k為c出現(xiàn)的次數(shù)