题目描述:
LeetCode 821. Shortest Distance to a Character
Given a string S
and a character C
, return an array of integers representing the shortest distance from the character C
in the string.
Example 1:
Input: S = "loveleetcode", C = 'e' Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
Note:
S
string length is in[1, 10000].
C
is a single character, and guaranteed to be in stringS
.- All letters in
S
andC
are lowercase.
题目大意:
给定字符串S和字符C,求S中的每个字符距离其最近的C的距离
解题思路:
正反两次遍历S
用变量lastC记录C最后一次出现的下标
Python代码:
class Solution(object):
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
INF = 0x7FFFFFFF
N = len(S)
ans = [INF] * N
lastC = -INF
for i in range(N):
if S[i] == C: lastC = i
ans[i] = min(ans[i], i - lastC)
lastC = INF
for i in range(N - 1, -1, -1):
if S[i] == C: lastC = i
ans[i] = min(ans[i], lastC - i)
return ans
本文链接:http://bookshadow.com/weblog/2018/04/22/leetcode-shortest-distance-to-a-character/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。