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 string S.
All letters in S and C are lowercase.

分析：
找S中所有元素距离给定C的最小距离，注意数据长度10000，说明n^2不行

思路：
先将S中所有的C的位置找出来，然后以这些位置两两为一段，对这一段中的元素判断离那边端点更近就OK，-1处和len(s)处默认有一个，这两个边界问题注意处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def shortestToChar(S, C):
    res = [-1] * len(S)
    # 找到所有的C的位置
    for i in xrange(len(S)):
        if S[i] == C: res[i] = 0

    # 左边界定为-1
    i = -1
    while i < len(S):
        j = i+1
        while j < len(S) and res[j] != 0: j+=1
        for k in xrange(i+1,j):
        	# 如果在左边界
            if i == -1:
                res[k] = j-k
            # 如果到达右边界
            elif j == len(S):
                res[k] = k-i
            # 在中间
            else:
                res[k] = min(j-k,k-i)
        i = j
    return res