Given a string
S and a character
C, return an array of integers representing the shortest distance from the character
C in the string.
Input: S = "loveleetcode", C = 'e'
Sstring length is in
Cis a single character, and guaranteed to be in string
- All letters in
This demo uses a generator to generate 2 lists:
one list (clist) stores position where letter equals to C, the other helps to output the final return list, which calculate every distances between letters and clist elements.
However, most of the distances calculation are not necessary. Thus, this method is simple to write, but not the fatest.
This method uses a stack data structure. stack
append and stack
For each screened letter, it compares two distances.
My solution avoid most of the meaningless calculation in the most simple one, so it’s a litter bit faster.
The main point of my solution is to generate an interval defined by
right. We have to screen string list used
enumerate from left to right.
index points to where we are, if we are in the interval, we have to compare distance to
right; if not, we have to redefined
right, then compare.
So for every letter, there are only two distances waiting to be calculated and compared.