Title: Shortest Distance to a CharacterSource: leetcode.com
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.
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
''' https://leetcode.com/problems/shortest-distance-to-a-character/ ''' class Solution(object): def shortestToChar(self, S, C): """ :type S: str :type C: str :rtype: List[int] """ lns = len(S) i = 0 indx = [] ln = -1 for c in S: if c == C: indx.append(i) ln += 1 i += 1 # Start populating the output i = 0 output = [] while i <= indx[0]: output.append(indx[0] - i) i += 1 j = 0 while i < indx[ln]: if indx[j+1] == i: output.append(0) j += 1 else: output.append(min(i - indx[j], indx[j+1] - i)) i += 1 while i < lns: output.append(i - indx[ln]) i += 1 return output |