# Problem 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:

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.

# Good solution for simplicity

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.

# Good solution for efficiency

This method uses a stack data structure. stack append and stack pop.

For each screened letter, it compares two distances.

# My ugly solution — faster than 71.17%

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 left and 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 left and right; if not, we have to redefined left and right, then compare.

So for every letter, there are only two distances waiting to be calculated and compared.