题目描述：

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:

1. S string length is in [1, 10000].
2. C is a single character, and guaranteed to be in string S.
3. All letters in S and C 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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码